It is indeed a limited pallete problem. If you're opening it in photoshop/paintshoppro/thegimp you want to go to the image > mode (menu options will vary) menu and change it from indexed to RGB or the equivalent. Now paint the red on - which will appear red - and then save it as a .gif again (256 colour in the gif options). That should sort you out.
Ok, short of me looking for the answer, please tell me how to display the avatars in firefox. I can see them in IE, but since moving to the other side I've been sorely lacking.
Comment