Well, they're one of the only "prog metal" bands of modern times that are actually progressive in terms of the evolution of their sound. Not only that, they're also one of the few progressive bands where guitar wanking is not the main focus of their music. On the contrary, most of the instrumentation is quite subdued. Pain of Salvation's greatness lies in their ability to write interesting concept albums with out-of-this-world sounding music, brilliant lyrics, and excellent vocals, yet somehow always escaping the stereotypical trappings of many other progressive metal bands. Not only that, the orchestration on their new album "BE" is probably the best usage of traditional instruments mixed with electric instruments I've ever heard.
Their music would be pretty hard for someone who prefers traditional or extreme metal, as there's a lot of odd vocal patterns, weird sounding riffs, and a wealth of "mellow" material scattered throughout their albums. Overall they're a difficult band to get into, and despite most of what I listen to being death metal and black metal, they still remain one of my favorite bands ever. All I can say is they require a lot of patience and a tolerance for mellower sounds.