Helpful tip: when you want advice about a certain tone, post a link to a clip of it, like so:
http://www.youtube.com/watch?v=nOSuObRNBUA
It definitely sounds to me like a stacked distortion, e.g. a distortion pedal into a fuzz pedal, or a distortion pedal into a driven tube amp, or two
cranked tube drive pedal in series, etc. More than one source of distortion, and probably two different flavors--one into the other. Experiment, it shouldn't be hard to get there.