Out of the "big four" -- Fedora, Mint, OpenSUSE, Ubuntu -- I chose to go with Ubuntu as I'd heard it has a big, supportive community; so there would be plenty of people to hold my hand when I get into difficulty, and plenty of (experienced) people to hit (and fix!) problems before I get near them. And its forums have already helped me quite a bit.
I also chose to install the latest long term support (LTS) release (rather than the latest, latest release) this time around, as it should be that bit more stable.
Ubuntu uses the Unity desktop by default (since 11.04 ?), but you can easily swap to one of the others (Kubuntu for KDE, Xubuntu for XFCE, Ubuntu GNOME, etc.). You can even leave all the desktops on your machine so you can boot between them until you make up your mind up about which one you prefer. For that reason I'm unlikely to drift away from Ubuntu because of its desktop(s). But I'm not enjoying Unity so plan to give KDE and XFCE a go.
Having succeeded with my laptop, I'm now thinking of installing Linux (prob. CrunchBang this time) on my netbook.
I have also bumped into some negativity about Ubuntu, but I've recently discovered (prob. not news to most of you!) that Google uses the latest Ubuntu LTS release (with a light skin over it) on their servers and desktops: so I'm more or less using "Goobuntu", for better or worse.
And finally, I can't help but notce that Linux Mint does seem to be getting a lot of good press these days.
Has Ubuntu lost it?
The truth about Goobuntu: Google's in-house desktop Ubuntu Linux
Linux Mint 15 -- The best Linux distro gets better