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.
How about a class action suit against PayPal? Anybody wanna join me? Stick it to PayPal and legitimize bitcoin all in one fell swoop.