I had exactly the same problem and tried re-flashing, cleaning the SIM card, the contacts, bending the pins, piece of paper/card behind SIM card, etc etc etc but none of them worked. Eventually I returned it to Nokia "care", and after a couple of attempts to fix it (ie they ignored the problem description and simply flashed it and sent it back), they replaced my N900.