An animated gif is a sequence of images (in your example, 100 images), and is technically possible - but obviously not suggested - open the file with the GIMP and edit each layer.
As you said, there are a lot of simple solutions for images with an alpha background (perhaps the simpler way is described here), but replacing a color is a bit difficult. There is an old GIMP plugin, the GIMP Animation Package or GAP, which is designed to work on multiple layers. Here is the answer to a question similar to yours.
Last version of GAP is for GIMP 2.6, but it seems to work even with GIMP 2.8 (read here).
Another way is use ImageMagick:
convert test.gif -fill "#fb8245" -opaque "#1cd000" another_color.gif
I've posted here just a frame, but convert works on all the layers. #1CD000 is the green to be replaced. You can also replace the green background with a transparent one, using "none" as a fill color (and adding an alpha channel):
convert test.gif -alpha set -channel RGBA -fill none -opaque "#1cd000" alpha_bg.gif
As you see, in the image there are a lot of boring pixels of other kind of green. ImageMagick comes out with the fuzz modifier (you can adjust it by trying):
convert test.gif -fuzz 15% -alpha set -channel RGBA -fill none -opaque "#1cd000" alpha_bg.gif
On ImageMagick websiste there are a lot of pages related to generate or modifying animations. Try and enjoy!
For a more professional work in my opinion you need an animation specific package.