Can someone mentor me through a project, please?

I've found an animated gif that I like, but I want to use Gimp to recolour it - ideally, I'd like to effectively redraw/reconstruct it (beyond the copyright line) but when I try to use the colour menu, most of the options tell me "XXX operates only on RGB colour layers."

I tried saving the gif as a xcf in the hope that that would make the colours available, but it doesn't. I even tried painting over it, but the colours are wrong when I paint (like I choose bright red and the brush paints brown).

As you can see, I haven't a clue what I'm doing and I'd appreciate it if someone could 'teach a man to fish' on this project. Hopefully (no guarantees) I'll only need a nudge in the right direction every now and then, rather than a step-by-step tutorial, but at the moment I can't even get started.

Any volunteers?