Think about this one moment the Megaman X series X, Zero and Axl would be perfect for the game, I know you said only 1 or 2 so if you cant make an exception eliminate Axl then. X power attacks can involve his armors and Zero's attack can be the ones from the game like hauduken. Rayman, Crash Bandicoot, Spyro, Prototypes main character (forgot his name), Sonic (Iknow Nintendo already put him on theirs but Sonic also made games in ps and in my opinion more in ps than in nintendo just saying.
-Zero (megaman x)
-X (megaman x series)
-Alex Mercer (prototype)
-Riku (kingdom hearst) his Sora's childhood friend better that Ansem because has more power options and was longer in the game that Ansem.
-Sora (kingdom hearts) I think I saw him in your list so nice choice, much power options.
-Cloud Strife (final fantasy) Perfect choice too.
-Leonhart (final fantasy) good figther
--Pacman I will laugh but not bad
- Bomberman for the fun of it and comedy sence
Personally I just want X and Zero to be in it!!
Most of this characters have been on playstation since the playstation 1 and some made it to playstation 2 they should have special treatment because the would bring nostalgia to those like me have been on playstation since the beginnig. You said you wouldnt conside Goku, Naruto well try to think of them they are great characters and would bring anime fans (which they have a lot) into the game and more buyers, their licenses might be hard (dont know how that works) but you already got it for some games right try to think about them.
Why has no one suggested that Voldo from Soul Blade/Soul Calibur be added. He is probably the sexiest character in gaming, and is apart of one of the most popular fighters ever.
Not to mention the franchise started on the PS1 with Soul Blades, so it would be a nice reference for those who know their Playstation history!
Plus he is F***ING VOLDO!!!! Check out some Soul Calibur IV or V gameplay with Voldo and tell me he is not awesome in every way!
Please put ICO in PS All stars, I would love hitting people with a stick and perhaps Yorda could help him with some combo setups. +_+ I would also like to see perhaps Selvaria from Valkyria chronicles.