You hear horror stories about both (for Google e.g. http://news.ycombinator.com/item?id=2483609 , http://ask.metafilter.com/178634/How-to-get-Google-Checkout-...) . Granted- more about PayPal, but they handle a lot more payments for a lot more people. What nearly all these horror stories have in common is that they're gathering pre-payments/donations for some even in the future. You rarely hear it from those shipping physical or digital products.
Generally they're pretty good. They've got low fees, they work worldwide, no need for a PayPal account to pay, and you get the money quickly.
They're widely trusted by a lot of consumers as their refund policy is very buyer friendly.
On one of my sites I offer PayPal vs Fastspring as a payment choice, and well over 90% choose PayPal.