I've never had a problem with paypal before so I do not understand why they would randomly freeze a payment and want me to give more information.
Because the user said you ripped them off and never delivered.
Unfortunately, since (1) BitCoins aren't something phyiscal, and (2) the PayPal TOS has a clause about virtual currencies, there's not much you can do.
It's getting to the point on #bitcoin-otc where people will only do paypal with trusted users. But all the trusted users are using Dwolla, MoneyPak, or something like that.