How do I replace colors in a .gif?

I have a .gif file here, http://www.drigg.org/sites/www.drigg.org/themes/drigg_theme/img/header_categoriesbg.gif. I want the exact same image, only in red instead of blue. Is there a way to do this without the original.psd file? Or should I just start over from scratch? Thanks in advance for the help.

 

you only can redo it

 

What do you mean? Just make a new one? I don't have the original psd so I can't go off that.

 

yes if you don't have the .psd you need to create a new one

 

So I can't use the color replacement tool within photoshop? I found the tool but I just have no idea how to use it.

 

no I think this won't work because of the gradient

 

http://img262.imageshack.us/img262/7940/watjh4.gif
like that?
ctrl + u in photoshop

 

Yes! Thank you very much. Hopefully I can figure out how to the rest myself.