I had a similar thing happen when I first got my card. After a couple charges, it was shut down when I tried to use it at a grocery store. When I called customer service, I was told it had been flagged and they had tried to call me but couldn't reach me, so they shut the account down. For some reason, they tried to call my office number rather than my cell. There was something about cell phones not sharing info with the credit card companies, so they couldn't verify my account with my cell info??? It's been a while so I can't exactly remember the details.
In any event, in order to reactivate the account, they needed to verify my identity. It was a quick three-way call with a banking representative who verified my name and address and how long I had been a customer with the bank. At the end of the call, the Amex rep asked if they could have permission to contact me on my cell in the event this happened again so we wouldn't have to go through the verification process. I said yes, but I haven't had any more issues.
I didn't have the concern regarding phishing because I called Amex, but your experience sounds similar to mine.
Starting Score: ~500 (12/01/2008)
From what I understand, it's an identity / address verification thing.