Where you might be okay is that you verified their ID's. I'm guessing this means that you actually met them? Start by going and filing a police report, as this would still fall under fraud. Once you've filed the report you might be able to use that to hold off PP for a bit before they pull back all the money.
No, I didn't meet them. I verified their IDs via Localbitcoins. As far as I know they are in Kenya, I'm in the US. Somehow I doubt the Kenyan Police (if there is such a thing) is going to give my plight any attention.
Pursuing them legally might cost you more than the amount you *might* be able to recover so it's not really a viable option in most cases.
How about a class action suit against PayPal? Anybody wanna join me? Stick it to PayPal and legitimize bitcoin all in one fell swoop.
It's going to be a very hard battle and the chances of winning a class action suit against Paypal is pretty slim. Also it'll be pretty costly to execute.
BTW, How did they convince you to accept Paypal? Did they have previous trust on Localbitcoins?