The guitarist from the Sword wore a shirt for Hammers of Misfortune, which just put out the new album The Locust Years, which is absolutely amazing (though more in the style of freaky rock opera-esque sort of thing, they experiment a lot).
Try out:
Opeth, Katatonia, In Flames (older stuff), Immortal. To branch out a little, that is.
You might like some of the 'metalcore' people; As I Lay Dying, All That Remains, Haste the Day, Bleeding Through, Shadows Fall, Zao, etc. (people like to go "uurghh hurr you're retarded" when I bring them up, but it can't hurt to say maybe).
Power metal is tasty; 3 Inches of Blood, Kamelot (they're incredible), Dragonforce, Blind Guardian, Sonata Arctica, etc.
Allmusic.com is your friend.