Never had this problem with Pay Pal;however, I'd be as upset with my bank. I think there is a law that even if a check is postdated it can be cashed as soon as it is deposited. (It might just be a state law that I heard that about) I'd try an atm deposit with the check and see if it goes through. Good Luck.
I hear all kinds of crap about PayPal that's simply ancient history, the company is now owned by Ebay and is not some fly by night outfit. I've used them from day one and have never, ever had a problem.
You'd have to check your countries laws on the matter, but I'm pretty sure Joe is right - you should be able to cash it straight away. I'd go that route, because dealing with Paypal over the matter is likely to be a long, fruitless process.