are you working in CMYK mode in photoshop? i had a similar problem on facebook, and after changing to RGB mode it vanished, so maybe...
map looks good so far!
just wondering, whats up with the rainbow islands?
cheers