My wife had this on one of her laptops that had an ATI Radeon card and she fixed it by turning on the KDE Desktop Effects via Configure Your Desktop >> Workspace Appearance & Behaviour >> Desktop Effects
Note, this is the default KDE Effects not the installed 3ddesktop / Compiz
I don't believe this but the above worked. I guess the effects handle redrawing the window. Now ready for the punch line...I hardly ever use KDE anymore and the problem is still there in LXDE/Openbox

I hate to tell you this but I have many ATI video cards and in my experience most ATI cards older than HD4000 seems to have serious problems running the fglrx video driver.
That figures. To quote Maxwell Smart, "Missed it by THAT much"

You might have better results by switching to the xorg ati driver from the Configure your computer, configure video card and select not to use the proprietary driver.
If I do that I will lose 3D though correct? If so I couldn't do that. If I can't play my games anymore I'll get the shakes

I see a new package sitting in the repositories, x11-driver-video-fglrx-8.920-1...Is that a new driver? If so any idea if that would help? --never mind. Tried the new one and the same thing.