"We weren't really adding any fees."  Uh, yes you were. 
 
I hate paypal.  Still use it, but fucking hate it.  I keep forgetting that I hate it, and go back to using it, and then something like this comes up.  Doesn't really affect me, but just reminds me how much I hate it. 
 
There are plenty of other options.  Western Union has a "send money with a credit card service"; you can always send a check or money order; there are escrow services (wherein both parties send money and merchandise to a trusted, disinterested third party, and after they receive both and payment for their services, they send both to their respective recipients).