I've used PayPal for years, had it hooked to my bank account, and have few complaints. I've been using them since the days when they were just a side project of the online bank X.com, which I was also a customer of.
Regarding account freezes; I've had this happen exactly once. The reason for it is that PayPal is extremely paranoid when it comes to the possibility of fraud; they take the "freeze first, ask questions later" approach. (This is not limited to PayPal; my first TAM was temporarily interrupted when Bank of America froze my debit card because of the "unusual" transactions in Vegas.)
That approach has its good points and bad points; I'm happy to know that if my account were compromised, there's a good chance PayPal would limit the damage post-haste. On the other hand, when they get a false positive, it's a mild PITA to get through to someone and have your account un-frozen.