Both distributions are good for first time Linux users. Linux Mint and PCLinuxOS are probably your best choice to start with as they come with multimedia support and desktop improvements out of the box.
Overall, Ubuntu is the best distribution at the moment but as a novice user you will find it lacks some things and you will find yourself struggling to add components which already work out of the box in Linux Mint.
My advice would be to start with Mint, eventually try Ubuntu as well and in a few years give Debian a try.
There's a reason why there are so many distributions. They all bring something different and you might like one more than the other for your own personal reasons (depending on your tastes, on your hardware, on your history, on your philosophy or even on how well you got to like the community...).
PS: Fedora is also definitely worth a try, it's not as easy as mint but it's a very rewarding distribution once set up correctly.
No matter what you choose you're likely to distro-hop for a while and I can only encourage you to do that as much as you can... it's a great adventure and there are more than 300 distributions out there, so you're not finished having fun