Some of the names are great (and I love the map), some I'm not so fond of, but hey it's your map.

One thing I've tried to do when naming towns, etc. is to consider the people of the area and their heritage and what kind of language they might speak. If its say a "viking-like" background, maybe you try to lean a bit toward scandanavian-ish sounding names. If its more middle-eastern perhaps you loosely base it on arabic names.

Just some ideas.