"Gorgoroth, Mordenkainen, Theleb Kaarna"
These are not exactly made up of english words either
I dunno, I actually think the random name generator is not too bad myself.
If you want to muck around with it, checkout the WorldNameRuleset.xml in your install folder. You can add stuff and it seems to work ok. For example, as a test I added this entry to the file:
So as far as I can tell, this basically means that when the generator is looking for a consonant to use, it will select the string "gorg" very frequently (Probability 0.6 is extremely high). I just started a 6 player random map with all custom factions to test this, and sure enough some of the initial cities have "gorg" in their name, for example "Lugorgiano", and "Gorgivonkaem". One issue is that it can select these consonants/phrases more than once though, so for example one of the cities was called Gorgigorgigorg In reality you would not use a probability as high as 0.6 and it might be ok.
I reckon if you mucked around enough (you'd probably also want to tweak the ProductionRules at the top of the file) you could get it to generate stuff more to your liking.
Alternatively as as NaytchSG stated, you could hard code the name of your first 10 cities.