I would also like to thank Chris for his answer, but can't figure how to add under his post! My experience was a little different and may be helpful to others. The iPhone 4S of a friend needed the screen replacing and it is OS5, but the date fix worked. I have never done this before or even owned an iPhone. I followed the guide here
iPhone 4S Screen Replacement
which is complete except it doesn't mention the front camera surround (a clear plastic ring with a bit needs to be prised off the old screen and put back in the phone body and the new screen put on from top so the surround thing doesn't fall out.
I am very meticulous and felt I did a good job, but got a continuous Searching. Telstra couldn't fix it! They did the sleep reboot and other stuff and wanted to sell a new phone! Going into settings general date&time, turning it to manual, setting it to current date & time, ejecting the sim card and reinserting it, turning airoplane mode off then on got it sorted. The last step was probably only needed to recheck as where I fixed the phone there wasn't good enough signal to pick up but going outside then turning aeroplane on & off saw it sorted.
I did as a "by the way" also connect to my wireless system before doing the above, this was just to see if that worked or not, but I was connected to wireless throughout the above procedure, doubt it is important but stating for completeness.
The unusual aspect to the above is this was an OS5 phone whereas others say it is an OS6 issue, it seems it is really a bug that has been carried on from earlier!