Much better than crap like Mastodon
Whenever I hear Mastodon mentioned, this is still the sound cemented in my mind.
I can't say I was ever a true fan of their old stuff, but I never really heard any of their music after they got "big" until recently. Whichever album I heard, the vocals sounded like a D-list Ozzy Osbourne. I got a kick out of the singing, but it's still not my thing. I'll take your word for it that their typical sound falls into whatever genre Monstro is though.
The song you linked, kinda of, just slightly, reminds me of the band Into Another.
Oh, and Mastodon pretty much formed because the rhythm section of the band were hired guns to play on this Today is the Day album.
It's kind of funny how many acts that worked with Steve Austin (be it playing with him, or having him engineer their albums) went on to become mainstream success stories.