How can I replace all red with black on the image below, using Photoshop, without damaging the image?
If you have the choice and can avoid using the magic wand tool, don't use it. It can work well on big images but not so much on smaller ones.
Since you simply want to change the image from red to black, you could simply:
Put that image in GRAYSCALE COLOR MODE
Then use the LEVELS (menu Image > Adjustments > levels)
This is a non destructive method and it will also take care of the anti-aliasing.
If the white part of your graphic is actually transparent, you can also simply use a COLOR OVERLAY in the layer style (double click on your layer for options), and select black as color.
You'll be able to change that color as many time as you want and keep the original color too if you want to revert to it.
Go-Junta has a good generalized answer, but for this specific image:
Lots of options, and while I do really like Yorik's channel approach which will work for this image, let me offer you what I believe is the easiest and probably best solution, which will work on all images not just yours: Hue/Saturation Adjustment Layer
Hue/Saturation Adjustment Layer, go to Reds, lightness to 0:
Photo from Unsplash.com:
Hue/Saturation Adjustment Layer, go to Red, lightness to 0:
Another one significantly more complex from Unsplash.com
Hue/Saturation Adjustment Layer, go to Red, lightness to 0... and then go to Magenta and drop its lightness to 0 too:
Yet another way, let Photoshop do the heavy lifting and totally non destructive method:
You can change this layer from black to blue to change the color to green if you like to change the color to green, see below and the layer stack as well. The black border around the green example is from the screen capture, just in case you are wondering.
There are probably half a dozen ways to do it, but a quick one is this:
1) Duplicate the layer the artwork is on.
2) Use the Magic Wand tool to select the area outside the white circle, then hold the Shift key and click inside the puzzle piece to select that area as well.
3) Make sure your background color is set to Black, then hit Cmd (Ctrl on PC)-Delete to fill the selected area with Black.
You'll now have two layers: The original red/white, and the new one which is black/white.
While typing this answer I thought of 3 separate but similar methods to get the same result, so there are many "Correct" answers!