+1 for Fedora. It's very stable even with very fresh packages, I've been on the same installation for years without a hitch.

I still recommend Mint for absolute beginners tho.