Yay, I have one level xD I use photoshop. I separate the different parts of the sprite in different layers and just change saturation/tint/contrast of each one. This way I can make them the color I want in seconds xD Although it does take 5~10 minutes to separate all the parts... But even then, it's quickier than changing the heads.
Anyway, if any photoshop user is interested in the .psd file of them, fell free to ask. Mine is photoshop v.7, but if should work on the new ones, right? xD
When I get some free time from school, maybe I'l post some others I have.