Beware people (like me) who offer solutions (like this)...
That said, here is how I have (several times) repaired this error on my HTC EVO 4G LTE.
(it's a Sprint phone, but I think these issues are across all of the telcos)
On your KEYPAD, type this:
##72786#
It will switch to a special mode with "SCRTN" as the Header.
Select the "Menu" button at top right of your screen, two options will appear:
Reset or Cancel
Select Reset
Stuff will happen automagically, and the phone will reboot. Cross your fingers & toes, and if you got it right, the phone will come up, and that error message will be all gone away...