ve al menu select >>> Color Range >>> ya ahí, presiona shift mientras arrastras el cursor (sostenido) sobre el color que deseas cambiar, entonces das OK.
Ahora en to paleta de color selecciona el color que quieres y vas al menu de Edit >>> Fill y le das Foreground color...
Vualá.... si tu selección fue apropiada debe funcionar...
Ahora que lo puedes hacer igual pero con Image>>Adjust>>Hue-Saturation, repite el proceso de presionar el cursor mientras lo deslizas por el color que quieres cambiar, entonces agregará un rango, mueves las barras de ajuste hasta obtener el color y ahí lo tienes...

De hecho me inclino más por este segundo método...
Hace tiempo hice un tutorial pero como lo postee en miarroba no carga el link, si quieres me dices y te lo mando por correo.
Saludos