Remove your sim card, Then hold the power button and the home button at the same time for 30 seconds until you see the apple logo, let it boot back up. put the SIM back in, and then turn it back off. and then back on. Sounds tedious, and it is, but it just may work for you.
i am also facing this shit ,, updating ios wont help..sure ,,ios 7 is best for iphone 4 or 4s..if u update ios it will be littile bit slower ,,nothing we can do to fix no service problem,,i dont know about service centre of apple .. i had done lot of ways to fix this,,,nothing worked,,, now i am not able to use this phone