I used Mercurial for three years, but started switching to Git about a year ago. I now grudgingly recommend Git to anyone who intends to be a full-time programmer. Git's interface is bad in many ways, which is the main complaint about it, and it's a legitimate one. It's just an interface, though, and this is a tool you're going to use all day, every day, in a wide variety of situations.
Here are all of the ways that Mercurial has harmed me, or that I've seen it harm others, and the ways in which Git does good where Mercurial does evil:
One: Mercurial is bad at handling large amounts of data. A friend accidentally committed a couple GB of data into a Mercurial repository. It became completely broken, to the point where most commands would die because they ran out of memory. Git has no problem with large data. It's awesome to be able to put, say, an entire home directory or ports install under version control without fear. (I recently put a multi-gigabyte Mac Ports install under version control with Git without even thinking about it.)
Two: Mercurial's repository model is clunky and stays hidden in the background (this is a bad thing; don't let anyone tell you otherwise). If you have a Mercurial repository whose size is dominated by a single, 20 MB directory, and you then rename that directory, your repository just doubled to 40 MB. This has limited my ability to manage real-life Mercurial repositories. Git's repository model is so good that I only hesitate slightly when calling it perfect. It allows me to think about what's going on in the repository with an ease that I never had with Mercurial, despite using it much more than Git.
Three: Mercurial is not safe. Both systems ship with many commands that change history, but Git's data model is such that even a "delete" isn't really a delete. Destructive commands just create new nodes in the history graph, then adjust the branch to point at them. Whenever this happens, the old branch HEAD is still accessible using the reflog. That's awesome, and it alone would bring me to Git.
Mercurial's answer to this is weak: destructive commands shove a bundle file into a subdirectory of the Mercurial repository; you have to manually manipulate it if you want to get the data back. Except some of the destructive commands don't dump the bundle files, which has made me lose actual data in the past. Even for the commands that do dump the files, keeping track of them, and which applies where, becomes difficult fast.
I'm sorry for recommending software with a confusing interface. But you'll be spending a lot of time with it; it's worth getting over the initial hurdle of confusion.
...until something better comes along, of course.