I get this also. I use to turn it off and that was such a hassle.
Then I thought of just using airplane mode so I wouldn't have to
Wait for the phone to shut off. I know this doesn't fix the problem
but it'll decrease the downtime.
Chances are Apple will direct you back to AT&T for a new sim card. They sometimes try to blame things on the sim card anyway so I'd imagine with a sim card error they may send you to AT&T for troubleshooting.
Do you have a case on your iPhone?
I am down on vacation at my aunts house, and of course I made her buy the iPhone 3G and hers is having the same problem. I then realized it was because the case is so tight on her phone it is pushing the sim try into the phone and it moves the sim out of the detector just slightly enough it doesn't notice it is there. I have been ejecting her sim and then just putting it back in and its fine. Then I put on the case, and I notice it gets tight again. She has the Incase silicone protector