I tried Red Hat back at version 7, but never got going with it I just couldn;t get my head round the Linux way of thinking and device support was not so good then.
My next forray into Linux came with Fedora, I had a better experience setting up but I found the X system full of little annoying glitches.
I finally plumbed just this month for Gentoo, now many will say this is not a distro for Newbs, but I am a Linux newb and the Gentoo handbook is very easy to follow. Also by the time I had been through it I had learnt so much by the time I had a KDE desktop up and running I was feeling more like an expert and so far I have got more out of using it as the install process has 'groomed' me along the way.
Also it runs much more smartly and cleanly cos you build Gentoo from source so it's more optomised for your particular hardware.
It's not for the impatient though !! installing KDE by compiling from source is easy with Gentoo (just one command: 'emerge kde') but it takes Hours !!! mine took about 36 hours on a celleron 1.3ghtz
Nice part about any distro that uses synaptic as a package manager...
You can install gnome with no problems. Don't limit yourself to Fedora and Ubuntu.
Try MEPIS, PCLinuxOS...both of those have LiveCD (try before you settle) installers...you can actually install from the desktop when you're booted up into it. Nice eh? Give those a go...you'll like them.
For a newb I recoomend SuSE 10. It has laods of softaware, a large following, nice hardware detection, easy installation and great GUI configuration tools. Also, when installing you can choose to have the Gnome desktop.