I've found that most users will trust PayPal and assuming a majority of your customers are from a region that supports PayPal, they probably won't object to using it due to this. However, when dealing with certain regions that PayPal does not support, you'll have to use an alternative such as Moneybookers which someone else already mentioned. I personally have not used that company but have heard many good things about them.