I photoshop I'll usually make a 10 to 20 pixel high gradient from one colour to another - it gives a nice selection of swatches to work from and maintain consistency with sprites.
Here's an example from a recent game.
<img src="http://fc09.deviantart.net/fs70/f/2012/237/b/5/wip_sprites_by_johnnysix-d5ccp5r.png" border="0">