I really like the new Sonata Arctica! It's very different of course, not even power metal really. I guess it would have been nice if there were more solos. It's kind of weird that a band that typically has a great solo section in just about every one of their songs suddenly does a whole album with.. I think at least half the songs don't even have solos!
Whoever recommended Labyrinth let me add a huge +1 to that. Return to Heaven Denied is one of my favorite albums! Get it ASAP! Dragonland is another great pm band, I love Starfall.