Have you tried Kuler? You can access it at www.kuler.com or you can access it straight from fireworks and place your colours in your swatches, it's very handy and full of what you need. To.learn how to use it to it's fullest try doing a search in youtube or google for kuler tutorials.
To access it in fireworks:
go to window>extentions>kuler
Hope this is good for you
When in doubt, visit your local paint store, or paint department in a hardware store. They have a full range of professionally designed "palettes" in the form of brochures. Grab a couple that you like, take them home and scan them. ;-). These brochures are usually theme-based, like "Spring" or "Merlot" or some such catchy title that summarizes the color theme.
Note I am not talking about the paint "chips" which show a single color in varying degrees of saturation/brightness.
I lIke Color Schemer 2 for Mac, and Color Impact 3 for Windows. Color4Design is good for Windows too.