I was going to come in here and post a huge list, but I’ve been beaten to virtually every band I was going to mention.  So I’ll settle for seconding a few of these bands:
Opeth - Truly one of the greatest bands out there.  I didn’t like the growling (“Cookie Monster” vocals) at first either.  But once you’ve listened to the songs a few times while reading the lyrics, you’ll get to understand them and appreciate them a lot.  If you still don’t like the growling, you might want to check out their latest CD, Damnation.  Not heavy at all, but a masterful album, nonetheless.  I’m sure some would disagree with me on that, though.
In Flames - The lead singer does quite a bit of screaming and growling also, but they are just so damn good!  My favorite albums from these guys are Colony and Clayman.
Amorphis - These guys started out as a seriously dark Doom Metal band, and have…heh…morphed into something truly amazing.  They released two albums with a guy who just growled, then for Elegy (one of the greatest metal albums EVER EVER EVER) they picked up a guy for clean vocals, and they took turns throughout the album.  They do primarily clean vocals now.  From the OP, I think you’d best like Tuonela, although I really like their latest called Far From the Sun.
Angel Dust - These guys are from Germany, and do straight up Power Metal.  They kick so much ass live it’s impossible to describe.  Albums to check out:  Enlighten the Darkness, Bleed, Of Human Bondage.
Katatonia - I don’t really know a lot of their older stuff, but their last three albums (Discouraged Ones, Last Fair Deal Gone Down, and Viva Emptiness) are all great.  Especially Viva Emptiness.
Lacuna Coil - My brother gave me a mix CD of this band and I had to go out and buy every album they’ve done.  Absolutely brilliant.  Unleashed Memories and Comalies are two CDs that have been in my rotation for over a year now.  And the girl they have doing lead vocals is really sexy, too.  
Nevermore - These guys are one of the first real metals bands I discovered a few years ago, and they remain one of my favorites.  The Politics of Ecstacy and Dreaming Neon Black are still two of my favorites, although I really like Dead Heart, in a Dead World.  Their newest one, Enemies of Reality, is an excellent workout CD, in that most of it just mindlessly heavy (not that there’s anything wrong with that).
Symphony X - I know you said you were already listening to these guys.  I’d just like to say that their newest CD The Odyssey is absolutely amazing.
Vanishing Point - I just discovered these guys a few weeks ago when I got a copy of Tangled in Dream.  I really like them.  The lead singer sounds like Dan Swano, but I’m not sure.  Check them out.
Wow, that went on a lot longer than I thought it would!  Good to know that there’s a few other metalheads here on SDMB.