This may or may not be helpful. But certain credit card companies use different security protocol. In the past I had to find a Canadian Bank that would work with the playstation store. Turned out about 1/3 of them at ps3 launch were not compatible with security verification used by playstation store. I was getting almost all of the transaction through and then fail, like you. It was something silly that with out google I would never have known. As I thought all Visa and Mastercards were equal.

If you know another american who has had no problem with getting the payment to go through maybe ask if they use same bank. You may be able to narrow down the issue. In my case I had no choice but to order another credit card at the time. Which will not help you. But some people feel better if they know why stuff didn't work.