I recommend Fedora, I mean come on Fedora 9 Sulphur is an infinately better name the Ubuntu 8.04 Hardy Heron.
A lot of people are getting Ubuntu, and there are a lot of good things to say about it. However:
From my experience, the installation of Fedora is just that bit easier than Ubuntu and the OS itself is slightly more responsive and cutting edge, but the Ubumtu interface is slightly more dumbed down after installation for the average winblows convert.
But then whether you choose Ubuntu, Fedora or Mandriva they all have good forums with helpful people who will guide you through and really, there is not much to choose between them. They do the same thing as each other and all do it much better than windows.