I'm finding that the name and city-name generator in Legendary Heroes (and ever since Elemental) is perhaps the worst execution of this sort of engine I have seen. Don't get me wrong, I love playing Legendary Heroes and it is probably my favourite game - but I find the random names it generates completely uninspiring.
You can look at single-developer games such as Dwarf Fortress or Distant Worlds and the names they generate are simple amazing and offer so much to the flavour of the game.
Legendary Heroes is an amazingly immersive game in most ways now - but then you end up with cities that sound like your cat has accidentally stepped on your computer.
I'd pay another $5 just to have DLC that corrected this - it annoys me that much.