Wow, that is a very drastic change from your initial version! But I like it a lot. It is missing the color the first one had now, which is fine if you're okay with that. If not, I would suggest giving the different countries a colored outline along the borders. It's very subtle but clearly seperates the nations. I don't know how to do it in GIMP, though. Here's an example of what I meant:
I can explain how I did it in Photoshop, maybe you can figure out how to do it in GIMP. I started with an ocean layer, then a white landmass layer (which I gave a black outline so it's easier to see). Then I made another layer for the black border lines:
Then I made a seperate layer for each 'nation' or province or whatever you want colored, and started coloring them in. I wasn't worried about going over the line into the ocean, because it's easy to select the landmass, invert the selection and delete whatever's outside of it on each nation layer. Make sure the layer with the border lines is on top though, so the colors don't go over it:
Do this for all nations, making sure no two neighboring colors are too much alike:
The next step is where I'm not sure how GIMP would do it. Photoshop has a function called Feathering. It takes a selection and basically dulls it, making it less jagged while also adding transparancy to the edges, depending on how much you feather it. In this case, I selected the contents of a nation's layer, feathered it 15 pixels and deleted it. It comes out as such:
Do this for all of them and the center is completely empty, while having a fairly nice (in my opinion) colored border along the edges, setting them apart in a subtle way. Top picture is the final result. Sorry for spamming so many images, I just thought it might look nice on your map, since you had colors for each nation/section/province in your initial one. Hope it's at least a little helpful, and that GIMP has similar functions, should you wish to try this. If not, I could give it a shot for you in photoshop and send you a transparant .png for you to put on yours!
EDIT: Could you tell me what icons you used for your cities? They look really nice!