I was in the same boat - being a long-time Windows user and wanted to try desktop Linux after seeing how awesome Maemo is.

A friend of mine said that it doesn't really matter which one you choose, because all the major distributions are good enough. All of them have their pros and cons.

I chose Fedora and stick to it now.
It is very easy to use and its community is very helpful.

(Although I still use Windows for work.)