Ubuntu is a good place to start. Make sure you have decent internet whichever distro you choose. It will work decently out the box, but you'll need a lot of googling and some apt-getting before you have an awesome box.
I Agree with Alt146, but if you are used to Windows, give Kubuntu (KDE) a try, as it eases you into Linux by providing you wth the windows look and feel. Having said that any Linux distro supplies KDE, so the choice is yours, K/Ubuntu will make your life easy when it comes to installing updates and programmes, due to it's slick Installer.
Has Kubuntu sorted out it's KDE issues? Last time I used it, it was slightly unstable. Generally I feel that you should a system design around KDE if that's the interface you prefer, but I haven't used anything that runs KDE in years, so I'm not sure what's good.
What's nice about Ubuntu is aptitude is really simple and there is tons and tons of documentation.
I started off with Ubuntu (Gnome). Ubuntu is very straight forward, you can't really go wrong there. After that I tried Fedora, Debian and Gentoo. Gentoo was the most involved, but once you know Linux well is quite a lot of fun to play with. But for someone new to the OS I'd suggest Ubuntu.
I would go Ubuntu or Mint. Mint is nice because it basically is Ubuntu with extra stuff, but Ubuntuforums.org has a very good community to help you out if you have trouble with linux.
Just kidding....my vote goes for Ubuntu as well. Soon you'll be able to upgrade to 10.04, which will enable you to shop online for music. Should be very very nice.
My first linux distribution was ubuntu, then Mandrivia , then fedora, then UBUNTU. I didn't find anything to compete with ubuntu. (from my point of view)