With photoshop you can change any color of any object you want.
1. After unlocking the layer (as it was explained in the previous tutorials), choose the Quick Selection Tool (W).
2. Select the area you want to change the color of.
3. After the selection, right-click with mouse, and choose the option "Layer via cut". It's going to creat a layer only with the selected area, as it shows in this image.
4. Now we need to creat a Hue/Saturation adjustment (indicated in the image). You can try any color of the spectrum, change the saturation and even the light.
You may need to change the order of the layers, so the effect doesn't show on both of them.
Here's the final result:
Before/After.
More examples:
