I still kind of like the dots... maybe it's just me but I feel like the map has enough going on already, you don't really need the extra noise from the same little diagram repeated that many times. Not that they're not cute little towns... but there ARE a lot of them.
I'm really glad you're not going with the white dots though (or at least you don't seem to be), the drop shadow seemed totally out of place =)
The map on the whole looks totally beautiful though! I stole a lot of inspiration from your mountain designs and drawing style ^^