Two useful sites for choosing color palettes, both from map-making backgrounds. They both consider qualitative, sequential, and diverging palettes as different needs, which I found insightful.

• Paul Tol’s notes, which gives special consideration to color-blindness. He has some visual demonstrations that picked up my own slight color-blindness.
• Cynthia Brewer’s ColorBrewer, with interactive elements so you can create your own palette for your particular needs.

Color Palette Ideas is different: palettes based on photographs, but can also be a good source for ideas.

As an update to my ancient blog post about this same topic, Adobe Color and paletton both have tools for generating palettes in lots of over-my-head ways. And Color Synth Axis is still very appealing to the geek in me, though it needs Flash, and so I fear is not long for this world...