A couple tips that should help immediately:
• If you're using an ink-jet printer then print on a photo paper. Plain papers are quite absorbant so the ink dots spread giving you dark, muddy colours with very little contrast. You can find photo papers in matte and gloss finishes.
• Familiarise yourself with the Unsharp Mask filter. It will punch up the contrast without messing up your colour values. Good use of this tool will even help get a decent result when printing to plain paper with an ink-jet printer.
• Check your images in grayscale. If there's not enough contrast in the gray, then there's definitely not enough in the colour version. Also, any area that's darker than 80% black in greyscale is going to be bumped up to almost full black when printing on an ink-jet printer. I had a look at your atlantis image and the ocean and forests are virtually identical in the grayscale and both are in the very high 80s. Your plains are in the mid 60s and only the mountains actually drop below 50. The reason your icons are popping excessively is that they actually have an appropriate amount of contrast on them while the rest of the image has almost no contrast at all.
More long term, if you're looking to get into cartography for print then there's a few things you really should take some time to learn about. Find some good tutorials on the art of trapping for print. You can probably find some useful stuff by looking up comic-book colouring techniques. Short version of what you need to know is:
• When illustrating for litho or gravure printing you should always work in CMYK from the start.
• 300dpi is good for the stuff you're doing, but if you have crisp inked linework that you want to preserve it's common to work at 600 dpi with a non-antialiased black channel.
• The percentages of each of the 4 ink colours should never add up to more than 300 (or 250 if the colour block is quite large).