I'd try resetting network settings first.
Obviously you've already restored, so if that doesn't work I'd call AT&T. Have you had any interaction with them recently? I called a few weeks ago to ask about adding a second line (didn't go through with it) and they ended up switching me from "Messaging Unlimited" to "Text Messaging Unlimited" the only difference being loss of MMS capabilities. I could still "send" them but they would never get delivered, and I couldn't receive them at all.