This also happens if the SIM Card reader DIES in the BB.
That's how my 9000 went to it's grave. During the first 8 months, I got this error, and the dreaded SOS signal and took it in and had the SIM replaced 2 or 3 times (I can't remember now).
But, then, it started happening over and over. I went through 4 SIM cards in 2 months. Then, Memorial Day weekend, I was in Florida visiting my GF and on my way to meet her for lunch. It had done this twice on the drive down a few days earlier and I would just "Re-Seat" the SIM and everything was fine. This time, the SIM didn't take, so there was an AT&T store on the way to meet her. I figured "5 Minutes and I'm on my way."
We put in a new SIM, didn't like it. Re-seated it, no go. Tried the SIM out of the AT&T Clerks BB, no go, but my new SIM worked in hers.
We tried 3 or 4 SIMs only to realize the SIM reader was DOA. We tried cleaning the contacts with alcohol (You might try that), but, honestly, I say take it in.