I've never heard Metal purists hating on them. SLUDGE purists, yeah, but not metal purists.
Hm, you know, metal genre purists are worse than indies. I really believe that
No-one is quicker to hate on a band that's had some success than the "die-hard" metallers on the interwebz.
With that said, Mastodon are the "perfect" metal band, in my opinion. They've got everything down: the style, the lyrics, the substance, the attitude, etc... Listening to "Crack the Skye" really makes me think, "yeah, this is what metal is all about and this is why I love it."
Of course they can't touch the legends but maybe 10 albums from now they'll be in a position to compete.