So I've finally switched from KDE 3.5.9 to 4.1.2. I tried to do a similar move in the past, but I got really disappointed in Plasma's performance back then. I decided it was my debug enabled build and fled back to where I came from and waited a little bit more.
Now the KDE 4.1 packages finally hit Portage, I tried another time to switch. But again, Plasma's performance in non-debug mode was still really poor. Opening the context menu took several seconds, moving Plasmoids was very sluggish and minimizing windows such that the desktop becomes visible wasn't smooth either. The hardware shouldn't be the problem, a 4 year old ATI Radeon Mobility 9600 should be able to do these simple operations.
I decided to start off with a clean xorg.conf. My current one was generated by the fglrx drivers, years ago, and it has turned in one big mess. But after Xorg -configure Plasma was still slow. After some Googling I hit this page, discussing the MigrationHeuristic option. But I decided to enable every option mentioned in the configuration snippet. It turned out to be a good idea: Plasma was smooth all of a sudden.
Being not exactly sure what caused this improvement, I tracked down which options really made Plasma more-or-less fly. MigrationHeuristic didn't matter, it were the following options in the Driver section which did the trick:
Option "AccelDFS" "true"
The first option was also mentioned on our Userbase pages, but the second option was definitely required to make Plasma perform well. Excellent, another problem solved.