Are you on cellc or virgin? then switch the phone to gsm mode only. i had that issue, it tries to connect to the 3g network which is running but not enabled for normal sims
No, I'm on Vodacom, but my network mode is set to auto.
I tried flight mode on and off, but it did not work for me.
Initially I suspected an app, but it's happened once more after uninstalling the app.
This doesn't seem like a common problem, so I'll do a factory reset to see if its sorted.