Yes, Paypal do sometimes have problems, but if you follow their rules and regulations and don't build your business around them you should be okay. The majority of horror stories are knee jerk reactions to an unfortunate situation which are never reported on again when a resolution is found.
The reason Paypal have such over zealous fraud checking and don't hesitate to lock accounts until they're 100% sure it's legit is because of how large of a target they are for fraud and also because of how accountable they will be. If someone sends me $10 and I run off with it, Paypal will have to pay out that $10 from their own pocket to the customer, might be okay on a small scale but at Paypals volume...
Personally I think the best method is to have a basic merchant account (authorize, nochex etc) and also Paypal, use your merchant account as the default credit card processor and also offer Paypal for those who either have Paypal accounts or are only comfortable with Paypal. If you're smart about how you use Paypal you'll be fine :)