pain of salvation is definitely one of the best progressive metal bands. their emotional songs are never cheesy (like dream theaters soft songs can be...you know i'm right!!) and they have a very unique style. the perfect element, while not really having much metal on it, is awesome and made me think of a funked out pink floyd. gildenlow's vocals are also very unique, its all over the place going from a whisper to a growl-like sound to a crescendo that peaks at a point that would make labrie jealous. and he doesn't belt out and hold those high notes, either, he uses it to accent the phrases. and sometimes the vocals are very rythmic, emphasizing the funk/jazz metal style that they play with.
and as for katatonia being progressive, i'd say that its a possiblility to get away with calling them that. i mean, just look at some of the crap that gets labeled "prog-metal." for example, savatage (they are horrible!), stratovirus (what the fuck?!), and even rhapsody (oh hell no!!). so why not push out the crap and allow katatonia. they may not play with lightening fast speed or have stereotypical prog-metal 80's vocals, but neither does opeth, and anyone who says opeth isn't progressive is an idiot.