I don't know if this is possible, but could you replace the Paypal client with one that transfers to major Credit/Debit cards instead? There would be more trust involved here, but I know that wouldn't shy me away.
For a while, Bitcoin Gateway exchanged Bitcoins for debit/credit card funds, and that's actually how I got my first coins. The problem is that credit cards (and debit to a lesser extent) also have the same chargeback/fraud issues that PayPal has. The only reason Bitcoin Gateway was able to work is because the guy manually called up the bank to make sure it was actually your card, and then called you personally to confirm the order, using the phone number on file with the bank. It was a lot of manual labor and because of that, it couldn't scale to the size that CoinPal/CoinCard reached.
I see. I do love how CoinCard is just a simple click of the mouse.