Thanks for your comments so far, I tried to keep them in mind as much as I could. Below you'll find the most recent iteration of my map.
I adapted the gradient glow like Chiashio suggested, though I'm not sure it's enough. I also added the city icons like I promised, though I'm not particularly happy about them just yet. I created the icon myself in Inkscape - you can find a fairly large version of it here. Also, I'd like to know what you guys think of the borders I added. They're simple red dots with a shadow for the moment, but I guess I could turn them into a solid line if that would be easier on the eye.
My biggest concern is a nice typeface for the place names... I guess I'll have to start messing around with fonts and such. Yaay!