I agree with Aang about the shadows. As for the labeling, I would label the places directly over where they're located instead of drawing a line to them. If its difficult to make out the labels that way you could use a subtle outerglow around the labels. This would also free up some space to write different things about the world or depict what some places look like.

I really dig the style of this map