I also have the same problem with MTN showing No Service. Have to switch of and on again and connects. iPhone 5 - 6.0.1 and MTN 13.0.
My wife has an android phone and she also gets this problem with MTN
Seems to happen mostly when I am in a lift (30 floor building in JHB CBD) going up to the 29th floor. Signal drops and switches between edge and 3G before it eventually loses all signal. Then when i walk out the lift.....tada.... "No Service". Reboot required.
I am now getting similar problems regularly:
"No Service" comes and goes sometimes three times a day, sometimes fine for three days
People call me, phone doesn't ring
People leave voicemail, I get no notification then suddenly on Thursday I'll get notified of 5 "new" voicemails dating back to Monday
Live in paarl so unlikely LTE but will try with it off