I just don't think she should be in the game. She has one downloadable game to her name, and many hadn't heard of her before AllStars. She's certainly not a playstation allstar.
I understand a playstation allstar as someone like Crash or Spyro. Fat Princess doesn't meet the criteria that they do, and I personally wish all the characters in this game had to meet those criteria. I wish that characters weren't being put in this game for the sake of capitalism, and that they were simply being put in for nostalgia and for celebration.
Crash, Spyro, Abe, Lara Croft, Cloud, Dr. Don & Dr. Dan, Parappa the Rapper, Gabe Logan, Raziel, Sweet Tooth, Spike, Sir Dan, Heihachi / Jin, Solid Snake, Tomba (well that's a personal one hehe), Ratchet & Clank, Jak & Daxter, Ico, Wander, Sly Cooper, Sev / Jan / A Helghast, Nathan Drake, Cole McGrath, Kratos, Nathan Hale / A Chimera, Sackboy, Toro Inoue.
It should just be characters from games that defined the platform exclusively and / or that have their roots on the platform. They could have taken more than one character from each of the respective games above.
Big Daddy, Dante and Fat Princess should not be in this game. The first two were generation defining characters, the latter is just a non-entity.
Also I'd hesitate to give Nariko and Kat spots. Heavenly Sword, like Enslaved was excellent storywise but as a game it wasn't the best. The reason people might associate it strongly with playstation is because it was advertised as a close to launch title but I don't think anyone really fell in love during or after playing it. It's the marketing alone that makes it iconic if you ask me, which just isn't enough.
As for Kat, I knew her about as much as I did Fat Princess, and while I've heard very good things about her game she still seems to me like she hasn't earned her stripes; she's just too recent and it feels like she's in the game solely for promotional reasons.