The ColorBrewer is fantastic for color classification schemes, but they aren't necessarily the best for the overall color palette of the graphic. I consistently find professional looking maps have colors that harmonize.
Not sure where to start? Here are 2 sites for color inspiration and palettes: Kuler and ColourLovers Both sites have loads and loads of color combinations and use descriptive tags to describe the colors. Need a color to represent "happy?" Type it is as a keyword and see what others think. The sites themselves are also nice examples of design -- good layouts, interesting use of fonts and the like. Check them out...maybe they will inspire you.
A new one to add is Daily Color Scheme
And the very interesting Flickr color pickr
Even shopping sites use color as a tool: Etsy color searcher