Download Gimp here
After that, install it.
Click on File, and select Open.
Select the picture you want to recolor, and click on it. Once it is displayed in Gimp, select the Colors menue:
From there, you can pick Hue/Saturation (which changes all of the colors in the selected area), and colorize (which colors the selected area all one color).
To select certain areas, you can use the freeform select tool, which is the 3rd icon in the top of the toolbox. it looks like a lasso. Use that to select certain areas (i suggest you zoom in really close by using Ctrl+Mousewheel) and then select the colorize menue to change the colors.
Make sure to save the new picture as a .png file.
Hope this helps. any questions, I will do my best to answer them, or give you a more detailed explanation if you need.
Edit: Maybe i should make a Tut on how to use gimp for things like this.... i think it would help a lot of people who don't want to buy Photoshop.