OpenSUSE is easy enough to use for gaming, and their KDE implementation is widely praised.
I've used OpenSUSE (11.1 Gnome) to play World of Warcraft in Wine. Installing proprietary nVidia and ATI drivers, the current development release of Wine, and huge amounts of other software is a snap (search their site for "1 click install" or "yast meta package"). OpenSUSE has truly extensive repos, and you're likely to find whatever you're looking for. Configuring EVERYTHING is done in YAST. Noodle around in there long enough, and you'll find what you're looking for.
Now, updating was slower than with Synaptic, but I think that was because they have different update protocols. Apt downloads all the packages, and then installs all the packages. Zypp downloads a package, installs the package, then downloads the next package, then installs it, and so on. But IMX, framerates were about equal in openSUSE and Linux Mint 6.
I've also used Sabayon Linux. Their command line package manager is called Entropy, and the GUI manager is called Sulfur. Sulfur is easy enough to use, but it absolutely pegged the meter for CPU usage. It also did ok with WoW, but doesn't have anywhere near the repos that ubuntu or opensuse does. I can't tell you if it will meet your other gaming needs.
BTW, game speed and KDE are not highly compatible IMX. I suggest UberBang (based on Lucid Lynx) or Mint LXDE if you want to stick with the Ubuntu base. I don't know how much RAM you have, but if it's plentiful (say >2GB), then you may want to disable swap space; you add the line "vm.swappiness = 0" to /etc/sysctl.conf. After that, disabling unneeded services will probably wind up having more effect on framerate than any other OS tweak, regardless of distro.