I use a Chase Visa card, and they've started charging fees like this as well. Chase similarly tacks on fees for international ATM usage from my Chase checking account. I don't do enough international travel that I've felt particularly motivated to find an alternative vendor, but my bank's fees for this, and other things, are starting to get to the point that I'm motivated to look elsewhere.
I keep all my retirement stuff with Fidelity. They're more than happy to act just like a bank account, with direct deposit, checks, ATM (with fee reimbursement), and the only major missing thing being a linked credit card. (You can get a Fidelity-branded MBNA card, but Quicken downloads would appear to require paying yet another fee.) I haven't asked them about their international fees.
Most annoying: I was travelling and there were no nearby Chase branches. I found a Washington Mutual, since they always had free ATMs, right? Wrong! Not only did WaMu charge me a $2 fee, but Chase charged me another $1.50 on top of that!
On top of all that, Chase seems to be working to engineer as much friction into the system as possible. Example 1: Chase's non-deterministic holds on large deposits. You can deposit a big check. It will show up in your bank balance when you check online. You can then try to do a transfer or something, and only then will you discover they decided to put a hold on your deposit (in other words, you end up bouncing checks if you're not careful). Example 2: Chase's new bill payment scheme. They used to just use CheckFree. You write an online check. Maybe a paper copy is printed, or maybe an electronic transaction happens. Whatever, but the money stays in your account until the other side actually deposits the check. Not any more. With the new system, they take the money out of your account first, then print the check, and you may or may not find out whether the other party deposited it. (In one case, they didn't and I didn't know for two months.)
Needless to say, I'm open to taking all of my Chase business elsewhere. The only reason I haven't bailed is that they've got an ATM in the student center, which is fantastically convenient for common-case transactions.