Much thanks for the detailed critique Hai-Etlik. I wasn't sure about the shipping routes, so I think I'll just leave them out. I also toned down the saturation a bit, warped the nation names, changed the texture, and fine tuned the nation colours. hopefully this version looks a bit more refined.
It's up to you to decide what you think is refined, or whatever it is you are after. I'm providing advice for what I think would improve it, and I am basing it on some experience with real world cartography, but it's up to you to decide if that advice actually helps you accomplish what you want. I my express things more directly for the same of convenience but there's always an implicit "if it helps you get what you want" in there.
Originally Posted by Rythal
"Warp" is a bad thing for text. It doesn't seem to be hurting you too much here, but "text along path" (or whatever Adobe might call it) is the way to go for curved labels. You don't want to distort the individual glyphs, only move and rotate them.
You might want to use some double curves, and try to pick curves that spread over the shape of the feature they are labelling by adjusting letter spacing. Unless the feature is significantly curved itself, you probably want just enough curvature to break the straightness of the label. If you can't fit a label inside the feature, fall back to treating it more like a linear feature (what you've done in "Milicia" is good) and if that doesn't work it's generally best to treat it like a point feature ("Cenia" might work better as a horizontal label next to the island rather than across it) Ideally you should be able to remove the borders, and still have a pretty good idea of the shapes of the features just from the labels. The tricky part is in fitting in labels for overlapping areas. Having a label cross over a coast line is something to be avoided, although sometimes it is unavoidable.
To get really good labelling, you'll want to do some manual kerning. Shifting individual glyphs around so they don't cross each other or any important features. This is helpful in fitting in labels for overlapping areas.