juanvaldez, I had the exact same experience last month with my new Blue Card, after having been a Gold Card holder with no problems.

I did get to the bottom of it when a merchant had to call AE for a verbal authorization. I asked to speak to the AE rep who told me the following: Some merchants have a higher fraud rate than others so AE is cracking down on it. In other words, a declined charge may be more of a reflection of the merchant's reputation than yours. Nevertheless, frustrating for the consumer.