Here's how to change all occurences of red, including semi-transparents, half-tones and shades, to blue. You'll keep your bright/dark nuances.
- Open the image with the Gimp.
- Set mode to RGB: Image > Mode > RGB
- Select the part where you want to change the color. Normally, you'd use the select-similar-colors tool. Point it to the offending (red) color.
- Desaturate the selection: Colors > Desaturate > Luminosity. Your selection will turn grey, all shades of it (assuming your images had shades of the sames color, why else would you be doing this?).
- Change the grey to alpha: Colors > Color to alpha. At the prompt box, use the color picker and point it to the same place you pointed to when creating the selection.
- Add a new layer (Windows > Dockable dialogs > layers). Make its background color the target color (blue).
- Invert the selection (Ctrl-i) and delete it (Del), so the new layer is transparent except on the places where you wanted to change the color.
- Move this layer below the rest.
- Save it, you're done.