About 3 months ago while trying to pay for an eBay purchase with paypal, my paypal account came back with similar messages and requests for information. I could not proceed. I called paypal and after a bit of screwing around got to a point where they would call me back at a certain time. It was about a 20 minute wait for the call.

The paypal person seemed confused as to why this had happened. Simply asked me a couple of my security questions which had been established years ago, reset my account and that was it. I've not had any problems since and did make it a point to monitor credit card activity for a while to make sure nothing had been compromised. I got the distinct impression while on the phone there was something that had happened at their end which they didn't care to share with me. That may be my own normal paranoia.