Okay, for recoloring sprites, close GIMP and use MSPaint. I do it the old fashioned way (pixel by pixel) but there's a lot of shortcuts you can find on Youtube and such. For recoloring big ol' things like this there's a very helpful tool in the paintbrush called "color" in the mode dropdown menu that changes everything you paint over with it to a hue of a specific color.
For recoloring stuff like 3D game art, I suggest you use the wand tool in GIMP and either increase or decrease the threshold to your likes. Then you change the hue by selecting, "Colorize" to your selected areas. It's not perfect, but that's what I use.