Even though you did a factory reset already, it's still worth trying Safe Mode to see if a 3rd party app is the culprit. Apps often reinstall automatically after a factory reset. https://support.t-mobile.com/docs/DOC-10696
So that error message appears in Safe Mode as well? I'd suspect some problem with the firmware, then. You could try reinstalling the firmware using Samsung Smart Switch.