Similar Issue
Hi mate,
I am having a similar issue to you.
Starting on Friday this week, the signal strength bar indicator showed very poor signal strength, then it started showing 'No Service' and also a message frequently popping up on the screen which reads 'New Voicemail'. So I went to the back of the house where the reception was better and called the voicemail number but there was no voicemail there to listen to.
This has been the same now for the last two days and I have tried to take out the sim card, give it a wipe and put it back in but the problem is the same.
My iphone is firmware version 1.1.1 and is jailbroken, I am running itunes version 7.5 and everytime I sync with itunes I am asked if I want to upgrade to firmware version 1.1.2 but I select no and then the iphone sync's fine.
I have also noticed that the usual 'clicking' sound when the iphone is used has a 2-3 second delay.
The iphone also shows the 'Repair Needed' message which it used to do before but a simple reboot corrected the issue.
I wonder if Apple have done a sneaky and updated my iphone anyway and now it won't receive a signal?
Any ideas anyone?