Open the picture in Photoshop:
Select the part of the picture you want to change the color of (use whatever method you prefer-quick mask, lasso, etc):
Remove the existing color with desaturate:
Copy just the part to be colored to a new layer (Command-J will do this)
Select the part you just copied. (Command-click on the thumbnail in the layer pallet to select it)
Set the foreground color to what you want to change the color too.
Fill the selection with the new color.
Change the layer style to Overlay
If you want the color lighter, adjust the Opacity
And now you have a new color!