Need help finding a Distro... but I have some tricky requirements.
Need something that wont take a whole lot of trouble to set up and use (my GF uses this PC too). But I need something that is bleeding edge in terms of Development software (Eclipse, GCC, etc...). And (that's the tricky part) ATI Catalist MUST work (ATI HD4850) because I do play some games.
Between KDE and Gnome I prefer KDE but I use gnome too, so no problem here. As a package manager I'm very used to Debian APT. But as gnome vs KDE I can learn to use another package manager.
Until you use a rolling release that is the normal case. Rolling releases are nice for some people, but it creates much more support effort than normal ones. When you closed some bugs new ones are found.
Arch Linux has a rolling release system and fits your bleeding edge requirements. Read more about them on their website and wiki. You'll get the latest GCC and Eclipse as and when they release. With a little work you should be able to get your graphics set up as well.
Arch Linux with their rolling releases would have been a good choice if they had not purged the proprietary fglrx/Catalyst driver from their official repositories. Now it is just a second-class citizen.
Gentoo also has rolling releases, but it is not trivial (although straightforward) to install. And Gentoo makes it easy to mix stable and bleeding-edge packages.
From the comments I gather, it appears that AMD developers only care about three distros, namely RHEL, SLED and Ubuntu (which you already use). So if 3D is a priority, you may want to stick to one of those distros.