In regards as to which is better for a newbie, I'd have to say that KDE is better for a total newbie.
Why? More control, more ease of changing things all through a nice GUI. Gnome you can of course change, but the graphics aren't as good, and I've found you do a tad more editing by hand rather than a GUI.
Which should you choose? Whichever you want. I personally prefer Gnome, however am using KDE for the moment mainly because it is easier to use it with SuSE and Gnome doesn't work 100% in SuSE, and also the fact I like the nice graphics (however Gnome can look nice too), but also more control via GUIs. Lots of people who start with KDE end up moving to Gnome, and then eventually to other things such as XFCE or IceWM or Fluxbox.