I just got off the phone with apple and ATT for the past 6 hours. YES SIX. And it took going all the way up to a senior advisor to get my problem solved. Some of the phones you buy from the store are set up to work with all carriers and some aren't. My replacement iPhone was not "officially" switched to ATT and was by default to Canada Bell. Now since this was my first restore since getting the phone the restore defaulted back to "Canada Bell" making my phone a brick. Only the senior advisors have access to switching this. It cant be done in the store, a new iPhone will not fix the issue. And regular chat support will not be able to help. I was put on hold forever why they discussed the problem. Apple can do it in store but they send it in to the tech people and it can who knows how long.
So he went in a cleared all the CDMA and other networks from my activation name so it was just ATT GSM only.
Good luck.