Anytime I see a notice resembling this, my immediate suspicion is that there is a third-party scam going on. This despite the fact that I've seen a number of such requests from apparently legitimate sources (notably NetSol). Note that URL within the PayPal domain doesn't mean you're in the clear -- it could be an inside job, and there are certainly ways and means for this to happen.

I'd forward the notice to PayPal immediately, and demand an explanation, as well as a public notice on their primary website. Otherwise you're risking far too much.

Looks like this has turned out OK for you in the end. Faith and trust in online transactions remain a major issue though.