One thing you can try, is setting the X server color depth to 16 or 24 bit and see, if things will improve. To change the settings, I use Sax2 (opensuse), Fedora or Ubuntu should have similar tools. After changing the settings you have to restart X, just logging out wont be enough, at least not under opensuse 11.0. The simplest way for me (with opensuse) is to press Ctrl-Alt-F1, you should see a console, log in as root, type "init 3", Enter, "init 5", Enter, then you should be back in KDE/Gnome, otherwise type Ctrl-Alt-F7.
