Gran Colombia, Italy, Khmer, Indonesia.
Gran Colombia may have lasted a short time, but had great influence over its region in South America. Also, South America tends to have a low number of civs, so it'll help make world map games more interesting.
Italy feels long overdue to me. You could have Rome and Italy co-exist like the Celts and England, or the Ottomans and Byzantium (who share the same capital, just under different names.) After all, as a unified nation, it's about as old as Germany (which always gets in Vanilla Civ 5.) The influence of the Italian states on the world in the past doesn't really get reflected with City-States.
Sure, many are tired of having lots of European civs, but Europe has been the world's most powerful continent for over half a millenium. A high population density results in a broad range of cultures despite its size.
Khmer would be nice to see back, simply to see Civ 5's take on the Baray. Hopefully it'll be somewhat more powerful in Civ 5 than it was in Civ 4 (Remember the Ballista elephant, with the "target mounted units in stacks outside cities" bonus? Ever actually used it?)
Indonesia is probably the most important on this list (though Italy comes close.) With Brave New World's focus on the latter part of the game, Indonesia's growing power of late becomes particularly relevant (and they have a long and complicated history to draw on as well.)
As a dark horse civ, I'd probably go for the Inuits. Maybe they get additional
from tundra and snow, meaning they can settle places others would struggle, and can send sea units under ice like Carthage can send units over mountains?