First I always jot some notes about the color I'm changing from and the color I'm changing to. Specifically, you will need to note the H S and B numbers of each color. You find that information by using the eyedropper tool to make the foreground and background colors the old and new colors. Now click on the foreground color and you will see the H S & B numbers. Note the numbers for both colors and compute the difference. If the old color is 106, 32, 56 and the new color is 219, 59, 57, the way to get from the 1st color to the 2nd is +113, +27, +1. I note this on a notepad or somewhere so that I can refer back to it.
Next use the magic wand to click on the color. If you select too much / too little, you lower / raise your tolerance number, deselect, and click the color again. If there are different areas of color to recolor that are not touching then you will need to have the box contiguous not checked. If you check contiguous, then the magic wand will only select the color in the particular place that you click.
Now that you have the HSB numbers, the difference computed, and your area selected you are ready to click Image (alt-I), Adjustment (A), and Replace Color (R). The fuzziness slider is the last thing that I adjust. In the preview box (make sure preview is checked), the white is what will be changed and the black will not be affected. The higher the fuzziness, the more other colors will be affected by the color change.
I type the HSB numbers in the boxes (the B number goes in the Lightness box). Then I play around with it until it looks like I want. I adjust the fuzziness, and then click OK.
Anyways, that's how I do it in ps7.