Everythings pretty much been discussed I think. A bit of a sum-up here:
1. What guitar do you have. I love my Gibson Les Paul, but if you want A LOT of distortion the Gibson CAN become muddy, because it has a big sound. In Heavy Metal for instance, where a lot of distortion is used many people play those ultra light Jackson, BC Rich, Ibanez etc. guitars, which give much more clarity with loads of distortion. If you use a Gibson type of guitar I would suggest to use less distortion and play more agressively, hit the strings really hard, it will make up for the lost distortion.
2. A good pedal is a must! In my experience Boss pedals are ussually crap on the distortion front, especially those Metal Distortions. Ibanez Tubescreamer is my choice, but of course that's a matter of taste. The Big Muff pedal is praised by many.
3. A problem solver could be: are you doing three finger or two finger power chords? If you're doing three finger power chords switching to two finger chords could be an option, don't know...
4. If you plug your guitar into the pedal and the pedal dirrectly into your console, then ussually a distorted guitar sounds like a vacuum cleaner. Mic your amp, or use a pre-amp.
5. If you are indeed mic-ing your amp, then the possition of your microphone is very important and even the room in which you record, or the possition of your amp in that room is important. Trial and error.