Version:           1.3 Beta (using KDE 3.1.94 (3.2 Beta 2), compiled sources)
Compiler:          gcc version 3.3.2
OS:          Linux (i686) release 2.6.0-test11

Just for information:
$ rpm -q XFree86-common
XFree86-common-4.3.99.14-38302cl

When switching desktops in KDE (using the panel or Ctrl+F1, F2, ...), it takes a long time to redraw windows -- a time extremely high considering I am running on a fast processor.

I've started seeing this behaviour maybe in August, which means it could be related to XFree86 version 4.3.99. I simply cannot test another version.

However, I have traced related this problem to the number of open konsole session with transparent backgrounds. I've noticed this message in my ~/.xsession-errors file:
kdesktop: virtual bool KPixmapServer::x11Event(XEvent*): request for DESKTOP1

and I noticed it happened in the exact number of times as I had of open transparent sessions -- all desktops counted. That is, even if I switched to a desktop without any konsole windows, this request would happen. 

It would seem to me that konsole is redrawing itself even for hidden sessions/windows at every desktop change.

Just to test, I removed transparency from all open sessions. The message disappeared and desktop switching became fast again.