This happened to me. After doing some troubleshooting with no success, I made an appointment with the Genius Bar. Basically, my iPhone "lost" it's IMEI number and forgot that it was a phone. Weird.
But I did notice that during one of the troubleshooting steps (restoring or recovery mode of DFU mode, I can't remember now) when the screen shows a picture of the cable and the iTunes icon, there is an info icon in the lower right corner. When I would tap on that, it would go to a new screen where it gives other info, among that, was the IMEI number. Mine showed all zeros.
This problem occurred for me after my brother was playing games on it. When I got my iPhone back, I showed off a couple apps to my dad, then put it to sleep with the sleep/wake button. I few minutes later, I tried to wake it up, and it told me to connect to itunes and restore. I tried resetting it first, and when that didn't work, I plugged it into iTunes to restore it, when I got the same SIM message you did, but I'm not sure of the error message number.