I might also add that if you are going to use a solid color to indicate each nation I think it might look odd because the ocean is also solid. I have seen maps that indicate borders by using a line which fades in towards the nation. Something like that might look better. Or just a line around the border that looks like a highlighter was used.

I would do Mid said and just take a look at some maps in the gallery and find something you think might work.