FWIW, the "replace color" tool doesn't work when the original has no color (ie, areas with saturation near zero). Lots of shoes are black, so the OP may be dealing with this limitation more than one might expect.
This is why, like RTC, I prefer using the Hue/Sat tool in colorize mode. Obviously, one needs to have a layer mask that only includes the shoe, otherwise the entire image will pick up that color.
For a slightly different effect, put a solid color adjustment layer on top of the image and set the blending mode to "color".
It's almost impossible to nail the correct color on the first shot -- it always needs tweaking -- so, don't even bother trying to use a brush set on "color" mode, or the actual "color replacement brush". It's much better to use a method that you can easily tweak simply by moving a couple of sliders.
That being said, these two brushes (on low opacity) are great for introducing small variation in the saturation or hue once you get close to the correct values using the other tools. This is tremendously useful for adding realism when re-coloring old B&W photos. For example, shadow, midtones, and bright areas of a specific material in an image, almost always have very different saturation values, and unless you make some attempt to simulate that variation, your re-coloring is always doomed to look somewhat fake.
HTH,
Tom M
