There is so much good metal, but I'l stick to bands similar to the ones you named.
After all (sounds a bit like judas priest)
Anthrax (well........ you might like it)
Cathedral (Dark and gloomy, vocals remind me of mustaine)
Other bands definately worth checking out:
1349 (This makes me think of the color black)
After Forever (female vocals,gothic, not like nightwish)
Arcturus (Gloomy vocals, violins, piano, etc)
Emperor (The emperors of black metal)
Falkenbach (nice vocals, folk metal)
Haggard (medieval, female and male vocals, violins, and whatnot)
Immortal (hell yeah ! this is what I call metal)
Impure Wilhelmina (soft,loud, heavy, another favorite of mine)
In Flames (I don't like it, but some I know rammstein fans like it)
Kitty (All female band, should I be ashamed for liking them ?)
Kreator (Uhhm hard to explain)
Leatherwolf (heavy metal, not much more to say)
Meshuggah (Unusual rythms, it's different than most metal)
Metal Church (Oldskool heavy metal)
Moonspell (Gloomy vocals, choirs. Check out Memorial their new album)
Morbid Angel (Dark gloomy powerfull stuff)
My Dying Bride (Dark, Gloomy, Dark and sad)
Napalm Death (Bald grampa's, heavy rotting vocal, anti-everything)
Nevermore (Amazing vocals, one of my big favorites)
Old man's child (regular black metal)
Strapping Young Lad (LOUD, powerfull, gigantic, enormous)
And much much more.