I would recommend Ubuntu Karmic to new users without much hesitation. I still like Linux Mint and Mandriva for the complete novice, but Ubuntu is a good option too.
If you haven't heard the Linux Outlaws podcast you're really missing out -- Dan Lynch and Fab Scherschel make a very entertaining weekly show that's not really tech-heavy, but more about the growing community coalescing around open-source software on computers and mobiles.
Dan does a great job of highlighting the changes in this newest release of Ubuntu, including the Ubuntu Software Centre and improved PPA support. If you're not familiar with either of these terms, they'll at least be easier to wrap your head around than the Synaptic Package Manager that came with prior releases!
There's also a Flickr slide show taking you through the entire installation process -- definitely worth a look if you've never installed an Ubuntu or derivative distro before.
And how was Dan able to grab screens during an OS install? Easy, it's Linux! 8-)
