Took my phone into ATT the first time and they replaced the SIM card.
My problem went away for a couple of weeks, but came right back. Went in a second time to ATT, explained my situation to an associate, and he immediately started a warranty claim. I got a refurbished phone within 3 business days and three months later, no error so far.
Just lucked out for me because the refurb took care of the NO SIM issue, was actually better cosmetically than the one I returned, and the battery life was WAY better.