@TheAccountant: What graphics drivers are you using? I haven't done any recent research, but last I checked, the open source ATI drivers didn't do 3d acceleration, so performance (for me) was always generally poor. The proprietary drivers are a must IMHO when running ATI.

I'm on a HP dv9000 laptop that runs @ 2.2Ghz intel pushing 2GB ram and would call it anything but slow.

Are you running the distros in a virtual machine, from a LiveCD or straight off of your hard drive? The former two will always be slower. In that case I'd suggest running something like openbox which is light weight and eat less resources than full DE's.

If it helps, I'm running ArchLinux with WMII, but even under KDE 4.4 it didn't take "a few seconds" for menu items to load.

[edit]
I don't think it has anything to do with the graphics drivers. I just downgraded to vesa drivers and Qt was still as responsive as ever.