Had that issue first time i used my Amercian express . Had to call them and tell them to allow it. Problem is that the charge comes from outside the US and credit card companies don't like that kind of thing.

At least that was the issue with mine.