Well, in that case, it'd be the user's fault for not having unique passwords, or at least for not changing an email password they knew was compromised, not Sony's fault. Sony can't do anything to ensure the users' email accounts are secure, so emailing a token would probably be the best solution.
Also, it's still basically impossible to transfer a land-line number to a cell number, as they are apples and oranges.
Often, every device in a secure network would benefit by having its own asymmetric encryption key. This way, Sony could have easily implemented a challenge-response that only clients could respond to. The hackers would only have gotten the public keys, which wouldn't do them any good outside of some sort of man in the middle exploit, which would require secret control of a part of the PSN network over an extended period of time.
Exception is maybe the credit card number, but that would mean that only a small subset of the original account holders can change their password.
Or you use a PS3 device ID and only allow changing the password on the device, but that is also known by the attackers and I'm sure it could be spoofed.
Not even sending a token to the email address on file would work in all cases because the users might have lost their email accounts to the breach too (by reusing the same weak password).