you can also use Paint.Net
which is what i used to recolor units for pac40, it is the exact same process. I will say though that you should keep the saturation low in numbers or your units will look like candy. and i would not touch the lightness, just lower the saturation even more if you want.
Re: PHOTOSHOP TUTORIAL: How to easily change colors of a unit etc.
posterizing color can sometimes make it a bit more cartoony especially if they are small enough. main problem i would think would be getting matching perspectives if using pictures to create unit images.
i think the way to go ultimately is with 3d models. PS isn't really the best tool for 3D but it does have some rudimentary capabilities.
BTW all you photoshop geeks out there photoshop turns 20 this month! (hard to believe for those who've been using it since before then). If your interested their having a podcast about it this evening:
I haven't done this yet, but I'm planning on having a go at it soon. I'm going to try and start with creating vector outlines from the images using vectormagic, cleaning up the areas of the photos outside the outline of the unit (by deleting those vectors in Illustrator) and then exporting to a bitmap file to tweak shading and colouring. The benefit of starting with a vector based image file is that you can scale it up and down cleanly, and legally speaking I'm pretty sure that constitutes a unique enough derivative work to at least the point of plausible deniability.
If anyone here has experience with unit artwork creation, or has links to other threads or guides on this please let us know. Here are some threads I found for background: