Hello Everyone.
I work at a IT Repair shop in Portugal and have a lot of experience repairing iPhones.
This started happening to me when iOS 6 came out and I had no idea what was causing this, since the hardware was all ok. Turns out that because the iPhone communicates with security certificates, you have to set the time and date right. Best way to do so is just connecting to a WiFi network and wait arround 5 seconds, then restart the phone. Otherwise, jsut set it manually (the year will be 1970, I think).
Once again, this is the solution for many network issues after unplugging the battery.
Hope it helps :)