For basic, ordinary use - paying for eBay and the odd purchase elsewhere, and once in a while, collecting a few bucks - I've had no problems with PayPal. But if I was planning to do a lot of sales in eBay, I might get a pro account, judging from the hassles others have had.
And yes, I have my checking account linked to my PayPal. It makes me a Verified user, as in I'm not some creep running a scam from Justanotherstan with a shell account, but I'm a real person with a real and known identity and credit history. Perhaps linking your checking account will smooth over some of your transactions?