I suffered along wilh you since 09/21/12, when I activated my iphone 5. I went through 4 or 5 reps and nobody had the answer. I even went to the ATT Corporate store and was told my phone was configured correctly. Finally, today, 09/26/12, I called Apple support and they set up an appt at the local apple store. Apple figured out that information from my backup was clobbering the cellular data network on my iphone. They restored it in the store and demonstrated to me that it was working properly. So what I have had to do since then, is hook up to itunes, restore back to the bad backup to get my contacts, upload the contacts to icloud, and then restore to the current software from last backup with download of contacts, apps, photos, music, etc! NOW my problem is, icloud is taking 3 hours to upload 85 contacts! Needless to say, I won't be using icloud in the future. ( And I know that it is not uploading my music data because I am only on the 5GB free icloud storage, and Storage & Backup is saying that I have 3.4GB of storage left.  At least I didn't have to wait for another iphone 5!