Looks good. I really don't think they're that obtrusive - especially not the roads/seaways (if anything, those might be a little too unobtrusive moreso, as occassionally they are hard to make out). As for the cities themselves, they're clear but not overbearing, I think.
My only comments/suggestions are:
1.) With the antiqued wood looking cartouche... maybe you want to go with a more antiqued or thematically similar looking symbol for the cities or vice-versa.
2.) What do the different colors of city mean? You might want to have something about that in a key/legend.