You might want to try out one of the other WMs, whether thats KDE or something less well known like xfce or openbox. I've myself been using gnome just about continuously since early 2.x and I may end up switching to something else as well. A nice thing with Linux is there's always a million alternatives, giving you a good chance of finding a close approximation to what you're looking for.

Also, something I've found extremely useful at both work and home is the compiz "Grid" plugin, which allows you to set up easy keyboard shortcuts for window placement. I think it can be found in "compiz-fusion-plugins-extra" on bunters. A video of it in action: http://www.youtube.com/watch?v=cHMKhiZmlV0

KDE 4.5+ has really come into its own, I highly suggest trying it out - I've been using it as my desktop for over a year now, and I've never looked back. One not very strong point is the KDE 4 application launcher, I'd suggest using a dock like cairo or you can configure the old gnome like launcher behavior to be default. I'm not sure how kubuntu looks, but fedora 14 and opensuse 11.4 both provide great kde experiences.

Old KDE fan where, moved from KDE to Gnome, then back and using Gnome for about 4 or 5 years now.

Last week I tried KDE 4.5.1 that comes with Ubuntu (I do so every now and then to see if I'll move back). After 30 minutes of trying to get Network Manager to start a VPN connection, and Googling for answers and reading the docs, I gave up and started the VPN connection from the command-line.

Now, I'm confused, how hard can it be to start a VPN connection? I clicked, I right-clicked, I reapplied the settings. Or it so simple that this long-time user can't figure it out?

knetworkmanager having a bug doesn't shock me, though my VPN seems fine in fedora 14 / kde 4.5.5. I did once have to start a wireless network from the command line after knm just refused. While not ideal, I'm sure you could run gnome's nm-applet instead - I don't think your vpn issue is indicative of a general kde quality issue, though everyone has their own standards. openSUSE 11.4 will be out on the 10th - it might be worth trying their livecd for a polished kde-centric view. I feel like Canonical commits most of their resources to their gnome build.

I'm thinking of just going back to old friend Debian (which I run on my Desktop). Ubuntu almost seems to be trying to be so friendly to newbies that it just gets in my way.

I'd suggest having a look at XFCE. It's similar enough to Gnome that you probably won't struggle to get used to it.

It's also been more stable for me than recent versions of Gnome and as a bonus it's much lighter on system resources.