I'm a bug fan of Adobe's Kuler for palettes. It gives several different methods of relatedness for your colors, and is really easy to tweak: http://kuler.adobe.com/
The interface is glitzy/flashy, but the “methods of relatedness” provided are unfortunately pretty much arbitrary (with respect to human color perception). Alas. If one does the trick, go for it, but don’t feel bad if one looks awful: it’s not you, it’s the site’s model.