Let us just assume for a moment that this is true.
My debit card info was on my PSN account. Now if I contact my bank and get a new card, I am totally in the clear from this mess?
Part of it. You accounts are good to go and they cant access your money. But you may still have your personal info out there that can be used to steal your identity (open up credit lines under your name). Its the second part that makes this so bad as the reprocusions from identity theft take longer to emerge and are much more costly to individuals
Edit: Yea what wargram said, to steal your identity people may try further phishing techniques. Just do not give out any personal info over the net to anybody, especially shady emails.