I have the same problem as Anthony. Wi Fi and everyting else but Carrier fine. Date toggled and now correct. With No Service showing, turn Auto off in settings for carrier selection and manually select a carrier. Indicator changes to Searching and a gray spinning beach ball appears to the right of the carrier selected. Indicator remains Searching until a Blue check mark appears beside the carrier selected. Simultaneous with the check mark, No Service reappears along with an error message that the selected cellular network is no longer available.
I get the same kind of error when I try using an old SIM card from another company that was replaced with a new smaller SIM when I upgraded my phone. In this case, I know that the SIM is turned off. So that is a clue about where the trouble lays. Its like the phone company itself is blocking the SIM. But with the ATT SIM that is giving me the No Service problem, I have spent hours online with ATT checking to make sure that the SIM is good by them.
I hope a fe more clues may help unravel this.