Have you tried the color replacement brush? I'm not sure what versions of PS it'sin (I use CS4) but it's in the brush tool sub-menu. Basically it allows you to sample a colour and paint over it with another one. You can use various settings such as color, hue, luminosity, etc. Might be worth a try.

Steve