So far I have gotten two really good suggestions from this site . . . thank you! I just bought Circa Survive and Deer Hunter (edit: also bought the dear hunter as per Ars - wow I need to pay closer attention. either both are good and completely different:). I'm impressed so far . . .
Here are my suggestions (oldies but goodies):
1. Paradise Lost: a band that had some turns musically, I strongly suggest listening to Icon (1995 or so), In Requiem (2007 or so) and Paradise Lost (self titled about 2008 or so). Their more recent efforts are pure gold to me especially In Requiem. Watch out, they took a big turn with the album One Second (which I liked) and the next two or three albums before returning to form with the two later albums mentioned.
2. The Flower Kings - big time prog-rock here, but completely awesome (imho). The main man is Roine Stolt who is from the sixties/seventies and has/does play with many notable musicians (dream theater). Check out Paradox Hotel, which is a heavy album to digest both lyrically and musically. Standout on that album is Monsters & Men. Give them a chance and I think you will find yourself humming the melodies sooner rather than later.
3. Mana - spanish rock group that churns out hit after hit. Not a dredg or anything, but a great rock band that has a good sense of melody and more importantly energy (I have seen them live 4 times). Recommend Suenos Liquidos, Amar Es Combatir, y Revolucion De Amor. You don't need to speak spanish to enjoy them. Lots of people don't like this, but I do. Best song ever is Como Te Extrano.
4. Others that may have been mentioned: Sigur Ros, Pelican, and Type O Negative.