Another credit union (which I have since left) in my area was a total nightmare to do business with. 6-10 transactions were met with shocking resistance and frustration. Check reviews for your propsective bank if possible.
When you do, try your best to do what I've done ever since my mortgage processor screwed up and double charged me: never use anyone else's online services; do all the banking that's possible from your bank's online bill pay. At least that way the people who are pushing money out of your account via automation report up through the same people who manage the rest of your account ;)
Also, credit unions seem to be happy to let you maintain an account with a balance but no fee in a way that banks aren't. As a result, I have my main checking account that I use for everything, and a second account at a completely unrelated institution where I keep 30 days worth of cash. I spent $10 for che(que|ck)s and an hour of time getting it set up, which was well worth buying me a month of insulation against any number of risks.
The most I accomplished was having a branch manager agree to waive 1 overdraft fee since I had never overdrafted my account before.
PayPal was even less helpful.
If I enable overdraft protection with my current bank (Wells Fargo) then they will charge me something like $17 to transfer money from my savings account to cover a charge that my primary account wouldn't have enough funds to cover.
This was a good reminder that I need to switch banks. Maybe I can find a good Credit Union in my area.