Losing network operator on Samsung Galaxy SIII mini
I experienced a similar problem, and it was caused by physical activity making the SIM card coming slightly loose, just enough so that the phone couldn't read it reliably. Try turning the phone off completely, removing the SIM card, reinserting the SIM card, and then restarting the phone.

If that makes the problem go away (at least for a few days), then it probably is the SIM card coming loose: maybe that specific phone is on the largest extreme of manufacturing tolerance, and the SIM card is at the smallest extreme. In this case, a little paper inserted alongside the SIM card, on the side without the contacts, could provide a more lasting fix.