I think this is it. And OBTW, for those that commented, last time I checked my credit scores, they were all excellent and nothing has changed.
When AT&T or any carrier conducts a credit check (which they clearly did) and then requires you to put up a high deposit, then they are required to send you, in writing, a reason for their decision. Look for it in the mail. It will explain why they came up with such a high deposit amount, and will list the credit reporting agency they used to base their decision.
Your next move should be to contact that agency and get a copy of your report, which they should offer for you for free.
I have no outstanding debt, no mortgage, no late payments.
That doesn't always mean your credit is good.
Most people will actually score higher if they have a mortgage with a good history of on time payments, than having no mortgage at all. The same is true having no outstanding debt: most will score higher if they have a small amount (10-20% of their credit limits or so) a history of paying those balances off, than they would by constantly having no balances at all.
Moral of the story, I guess ATT thinks you have to pay to play.
No, there's definitely something more to this, it would benefit you to find out what that is. If AT&T is giving you a hard time with deposits, there could be something you're not aware of that you need to correct on your credit report.
EDIT: One other thing. When carriers check your credit, they're not just using the typical credit reporting companies. In addition, they also using a "Telecom Decisioning Tool" that is meant to detect possible fraud. Companies like LightBridge, Equinox IS, Vesta, Neustar and IBM offer these types of tools. And I'll bet that rapidly opening and closing wireless accounts in a short time period has put you on their radar as a possible risk of fraud.
If your credit is spotless and AT&T wants 1 large to let you sign up, then I bet you have a fraud file with one of these companies after they've seen your Social Security pop up in their inquiry system one too many times. And it WILL affect you at other carriers, too.
Bottom line is, you need to find out form AT&T exactly why they put the brakes on your activation.