This is an update to my earlier post...
Since the late evening of the 16th, my 4S started behaving on its own. Since then it has consistently shown the correct time & time zone, correct location. Something has certainly happened out there, since around that time I also noticed that my iPhone 4 showed my location far faster and more accurately than before. I do think something was fixed, either by the Serivce Providers or something else, since several users have reported that their phones also started behaving after the 16th.
For those users who are still having problems, I really do feel sorry for you since I know how frustrating it can be. I suggest you try the procedure recommended by Apple to traceyfozz (see several posts above). Or just wait a couple of days, maybe things will settle down on their own.
On another note, I today upgraded my 4S firmware from iOS 5.0.1 build (9A405) to (9A496). Although I never had a "No SIM" or "Invalid SIM" issue, I did notice that, for example, when I exited an Elveator, my phone would take a while to lock on to a signal again. Now it seems a bit faster. It's not a big difference but it is there.
I don't think the (9A406) firmware will resolve the wrong location or time zone issue but as a last resort, there is no harm in upgrading. If you are already on 5.0.1 then iTunes won't automatically download the new build. So you will have to manually download the new build from here:
http://appldnld.apple.com/iPhone4//041-3417.20111215.Slnt4/iPhone4,1_5.0.1_9A406 _Restore.ipsw
Once downloaded, Option-click on the Restore button in iTunes and select this new file.
Hope this helps.