Mastodon's album before Blood Mountain, Leviathan, is what got me back into metal after the being turned off by the whole nu/rap metal stuff of the 90s. It's a little more cohesive than Blood Mountain because it's a concept album based on Moby Dick. No, really.
I'm more into the stoner/weirdo/experimental end of all things metal, but here are some of my recommendations:
High On Fire - their two latest records, Blessed Black Wings and Death Is This Communion, are absolutely fantastic. Guitarist/vocalist Matt Pike is like the second coming of Lemmy, making High On Fire the Motorhead of the new millenium. Check out the first track from Blessed Black Wings, "Devilution", as a taste.
The Baroness - Georgia metal band that sounds a bit like Mastodon crossed with Fugazi. The vocals sound more alt-rock than metal, but these guys are really inventive musicians without ever dropping into pointless technical wankery. Check out their MySpace page.
Amon Amarth - Part of the genre known as battle or Viking metal, Amon Amarth are like a live-action version of Dethklok from Metalocalypse - big shirtless European dudes who swing their hair in time to the music. They sing songs about Valhalla and the treachery of Loki, and really, isn't that something we can all relate to? Video for "The Pursuit Of Vikings".
Isis - Bands like Isis, Pelican and Cult Of Luna are part of what's known as "ambient metal", which means that they tend to play long, mostly instrumental songs that focus more on mood. Isis are pretty interesting in that they release a remix album for each of their "official" releases, where they let people go crazy with their music, which is the sort of thing I wish more bands would do. Their official site.