I received following message after I restored my iPhone OS to 4.2:
The SIM card inserted in this iPhone does not appear to be supported. How can I use my SIM?
Depending on your carrier, some SIM batches are known to be problematic (Bell is a good example). Outside of that, the most obvious is if the iPhone was jailbroken and unlocked, the restore would remove the modification and return it to proper function. If everything should be working legitimately, you can take it to an Apple Store and they can look up which carrier the unit is locked to (if any).