So (in case anyones interested) we did sim replacements to rectify this issue.
Turns out Samsung has an IMEI issue.
Their device is unable to detect the network and up comes the “Not Registered on Network” message. This occurs because after getting an update, your device IMEI number is changed to “SN 0000″ and it shows that your device SN number has been broken and need to be fixed.
In this situation the ‘Not registered on network’ error will show itself when you attempt to make a call or text. This occurs because your Service Provider is simply not notified of your IMEI number so on the screen you will see “Not registered on Network“.