It seems to me, the problem of trust and PayPal can be easily worked around..

All you need to do is follow the same approach as used by Bitmarket.eu and other such Bitcoin market sites. Setup a
new website that acts as an escrow service for PayPal transactions between buyers and sellers. Both parties would
have to be vetted and verified before they are allowed to buy or sell Bitcoins using PayPal.  Some criteria could
be used, i.e minimum length of time as PayPal user, registered eBay member with at least 99% feedback etc. You
could also have a maximum limit on the number of bitcoins in any one transactions, and a daily/weekly or monthly
limit to make it difficult to carry out fraud/chargebacks on larger amounts. These limits could be increased/removed
over time once a user has proved themselves to the community. The site could be feedback driven.

All purchases of Bitcoins could be indirect without any direct reference to Bitcoins on the PayPal transaction.
Some electronic product (information, ebook etc) could be the product, so that it doesn't break PayPal's policy
or rules.