Btw. Storm Rider, any bands you reccomend for someone who likes Evergrey and is discovering prog?
I'm not sure exactly how much you're familiar with the genre, so I'm just gonna list a few of the bigger (which is of course a relative term) bands off the top of my head, and if you've heard of them or like them, then go a bit deeper into the more obscure territory.
Fates Warning is an obvious choice, but I would advise starting off on their earlier stuff, as their newer material is more ambient. Unless you're not particular to prog
metal, in which case I could recommend a much larger variety of bands.
Symphony X is another of the more popular ones, and like Evergrey they have a lot of power metallish bombast to them, so if you haven't heard of them, you'd probably like them. Start at the end of their chronology and work back.
Star One's
Space Metal. Just buy it, trust me. Hopefully the more it sells, the more Arjen will want to do a second one. For that matter, his main project Ayreon is great as well, but less heavy and very, very diverse.
Nevermore, of course. They don't really fall into the regular 'prog metal' stereotype, as they have no keyboardist, but Jeff Loomis writes some of the best riffs I've heard, period, and he basically crams as many as he can into a 6 minute song. I got into them through Dead Heart in a Dead World, but any of their albums (except their debut and the un-remastered version of Enemies of Reality) is really pretty awesome stuff.
Kamelot, especially their newest album The Black Halo. Terrific disc, I just ordered it off Amazon on Thursday and am waiting anxiously for the tracks I couldn't find to download.
Hopefully that'll get you started off pretty well.
EDIT: I totally agree with Miseraetur's suggestion of Pain of Salvation as well.