PayPal & eBay (same company etc), though generally good sites, have notoriously difficult + time consuming claim/fraud procedures.
Not quite the same problem, but seems a chance to have a moan!:
I had some problems on eBay a while ago and have been trying to claim money back from them. After months of e-mails to their fraud department in Germany, they finally agreed to pay me, but only if I e-mailed my full bank details to them. I said that I wasn't prepared to e-mail that information and asked why they couldn't just credit the money to my PayPal account (seemed the easiest option, especially as they are the same company) but they refused. Months later I'm still waiting for my money (I posted my bank details to them by snail mail, recorded delivery etc in the end).
Phew! Rant over. Feel a little better

I totally sympathise though Jaguarpig. I hope that they pay you in the end, after all, they do owe you etc. Threaten to go to Watchdog or something.