These weird colors also show up in mozilla.
Gimp is almost unusable because of the colors. Try calling up the sharpen filter. The view window is so bad that judging the sharpness effect is a guess.
I upgraded my system 3/21/04 late in the day.
Found a fix in gimp, at least. Set display colors to minimum of 27. Now looks much better.
Noticed also that invoking realplayer renders distorted colors in the background screen.
it sounds to me like you have your video card set to 256 colors.
go to your /etc/X11/XF86Config file and in your "Screen" section you should see "DefaultDepth", it is probably set to 8. try bumping it up to 24, if that does not work go to 16.
you will have to restart X once the change is made. you can either log out and back in or hit cntl-alt-backspace.