I'd try Slackware 12. It's great if you just want to jump in and get your hands dirty. Slackware is great to learn on, because it is a fairly complicated distro, relying mostly on you, rather than Ubuntu, which is much more automated.
When I started, I used Slackware, and it taught me a very large amount about linux, by requiring me to learn how to use it to install programs and configure it. It's very complicated, but in the long run, you'll learn much more, and be much happier. Obviously it also has no adverse effects on you if you decide to switch later, which is what I did.
Jumping right in and treading water until I learned how to swim is the best choice for in my opinion. It's also great, because once you go to Ubuntu, many people rarely switch back to other distros. And plus, with the knowledge you gain, if anything goes wrong, you have a much better chance at being able to fix it.
I like Ubuntu, but I disliked how automated it was when I first started using it, because I found that I wasn't learning much. Sure, I had the option to try the harder way, but I'd always end up doing it the easy way, just because it was there
/endrant But seriously, I think Ubuntu is a great choice once you learn some stuff. Try Slackware.