I've achieved this effect in GIMP by playing around with the Tint and Color levels, accomplishing things like very convincingly changing people's eye color in photos (e.g. took a photo of a brown-eyed friend and gave her blue eyes). Also very unnatural -- but still convincing -- transformations, like flame-red eyes! The only trick to it is to be sure to first select the area(s) you want to change the colors in, otherwise you end up with your entire image going all wonky on you and looking like crap, and everything beyond that is just experimenting until you achieve the effect you want -- since that is a very subjective thing, I can't give you a step-by-step walkthrough because I don't know what precisely you want to change.
I have no doubt that Photoshop could achieve the same thing (probably with very similarly-named tools, in fact).