Just out of curiousity where do you have the PLSK.0000****.0001.sh located. I had that error once and it was as simple as moving the key into /root and doing the command
P.S. you may want to mask the key number so ppl don't know it as I did above.
mv: cannot stat `/etc/psa/psa.key': No such file or directory
even without your key installed there should be a /etc/psa/psa.key so it is wierd you are getting that error. Try reuploading the key using binary, not ascii. If that does not work then tell plesk about your problem using this form https://www.plesk.com/support/server_service_form/
they will resend your new key as ckpeter said, but just remember they just released Plesk 5.0 so they may take a little while as they are probably getting tons of support requests atm.