What you really need here is a combination of two things:
- Photoshop (costly, industry standard for a reason), GIMP (free, kinda lousy), Paint Shop Pro (free trial, usable), or some equivalent editing tool such as Paint.NET - thanks Scott Chamberlain;
- A version of your source image which has the elements of the picture on layers of their own.
Without the first, i.e., with only a simple bitmap editor, you won't be able to change the color of the foreground element without either inducing jagginess (pixelation) or messing up other parts of the image, because you can't work on it in isolation.
Without the second, you still can't really work on the foreground element in isolation, because it's blended into the rest of the picture at its edges. If you have the foreground trident (?) on its own layer, then you can change it as you like, and it'll be composed with the background layers to produce a smooth result.
You really can't do this with a simple bitmap editor; you need something with, at minimum, layers and a hue/saturation editing tool, so that you can just recolor the foreground element instead of trying to flood-fill it.
If you can't get a layered source file to work from, then you can probably use the "select contiguous", "magic wand", &c. tool in your chosen image editor to select just the foreground trident, then copy it to a layer of its own and edit it there. You'll probably have to fiddle with the edges a lot to get rid of the background color that creeps in due to the anti-aliasing, though.
The cross-hatched background poses an additional challenge, in that you're going to have a very hard time "lifting" it off the background with the selection tools, and a harder time still getting it separate from the foreground trident. To be honest, you may be better off recreating the image from scratch; to do so would require some knowledge of paths (i.e., vectors), but you'd be able to produce a much nicer result, and would get the extra benefit of being able to further edit it later on.