I've been living with this problem for 2 weeks not knowing it's a widespread issue, thinking that perhaps I got abroken Sim card.
After reading this thread (all 49 pages) and a fee similar threads on here and other forums, and after having tried various methos (hardware and software), I have the following findings (and have found a solution for myself).
Background:
iPhone 4S 64GB bought in first week of release from UK online store.
Model ND258B
Carrier Viettel from Vietnam
SIM normal SIM cut to micro size with stappler type cutter
Phone came with 5.0 originally. Put in SIM from iPhone 4, had trouble recognising at first and worked after many attempts. SIM with iPhone 4 no problem. When finally worked with 4S (didn't recognise at first, had to put in and out many times to recognise) the Phone section under Settings show My Number as Unknown. This is a key identifier to my issue and solution (see later)
Updated to 5.1 for a few days and started seeing problem:
Have to call twice to go through. Then signal drops. Then searching. Then No Service. Then Invalid SIM.
Had to reset for Phone to work for a few mins, then same sequence again.
Changed a new SIM card from Viettel (Normal SIM cut with stappler). Worked for 30 mins, then same problem.
Did a restore to new 5.1 (406) with newly issued SIM. Same problem.
SOLUTION: change my wife's SIM (different Carrier, different looking chip on SIM, normal SIM cut to micro size) from her iphone 4 TOgether with the SIM Tray and worked.
My 4S now showing correct My Number under Phone in Setting (before with not working SIM shows Unknown).
My "Not working" SIM from 4S together with Tray, works fine in my wife's iPhone 4, again, showing correct number under Phone/My Number.
So I believe this is a combination of many issues and many fixes.
For me, the identifier of a "good for 4S" SIM is that under Settings/Phone/My Number it shows your correct number, rather than Unknown.
My suggestions to to try find a solution in the following order:
1. Try Software first. If under 5.1, try Restore to 5.1 (406) and see if works. Can also try a DFU restore.
2. If you are on 5.0 now and working normally DO NOT UPDATE UNTIL FURTHER NOTICE.
3. If software fix doesn't work, try getting a new SIM from your operator. New SIM have more chances of working if it has different wiring on chip to your "not working" SIM. Micro or Cut from normal doesnt seem to make a difference.
4. Wait patiently untill Apple post a proper firmware fix. Many have reported sucess with software fix by updating to 5.1 beta 1 or 2 (Developer only). Some - no luck. That's why I guess it's still under beta.
For me, I will try to contact Viettel tomorrow and try to get a new SIM with different chip wiring to my current "broken" one. Will report back.