The problem here is Replace Color. Not because it doesn't do what it's supposed to do, but because nearly everybody misunderstands how it works. And that's the case here too. This comes up very frequently.
In digital images, "color" has a narrower meaning than in everyday speech. In digital images, the color and luminance components are stricly separate and independent from each other. A darker shade is not a "darker color" as you will say when choosing wall paint, it's a darker luminance.
The Replace Color tool works only on the color component. It does not work on the luminance component! If you have a bright yellow and you use the replace color tool with a saturated purple - what you get is a pale lilac. That's because the luminance is unchanged.
The reason this is so, is that blend modes wouldn't be possible at all otherwise. If color blend mode changed luminance as well - then you would just have Normal mode. A paintbrush in color blend mode would just be a perfectly standard normal paint brush.
And with all that said, I also think the replace tool is the most useless tool in all of Photoshop. It's a destructive tool in the worst sense, impossible to tweak once the stroke has been put down. The proper way to do this is to make a mask of the desired area, then use any of the more sophisticated adjustment tools Photoshop has to offer.