Replace black with another color?

It's because black is a lack of color, rather than a color.

I often find the easiest and most natural-looking way is to do Image - Adjust - Curves, then move the black points of the various channels until black is turned into whatever color you want.

If you really want to isolate just black itself, without affecting other dark colors, you can use the Magic Wand selection tool to select just the black parts first.  Depending on your image you may want to change the tolerance.

Finally, for really advanced needs, you might consider turning the image luminance into a selection (or layer mask), then using curves on that to isolate just the darkest parts.  The advantage of this is that, unlike the Magic Wand, the point and steepness of "roll off" from black to colors that won't be affected by your subsequent operations is fully controllable by you.

-Noel