Something similar to this happened to me recently.
According to the suggested actions in the post:
Do take the device into the dealer and make them explain what those messages are. If they can't figure it out ask for their security department contact details.
Do contact the security department for the devices service provider. Ask them to either monitor the account and traffic for suspicious activity or send them the device for imaging. Their hardware is put at risk instead of you own.
Do not plug the device into any computer; not even for forensics! I've already heard one horror story that didn't end well when an infected phone touched a PC in a USB way.
Do not allow it on your local Wi-Fi network. While I've not seen malware jump over Wi-Fi in the wild (between phones and PC that is) I've tested if possible on Android and it isn't hard.. on my own devices only (I'm not a distributor) which you can read up on it at Stack Overflow where I've detailed how to get Android running Metasploit.
The first one is practically impossible now since I was out of town and was using a different service provider when it happened and the message was apparently sent by the service provider.
Now, I'm wondering if it's possible for malware in Android to hide out in hardware's firmware like in some cases with maybe a laptop's keyboard or BIOS to survive reinstall?
Is it safe to backup the files in the phone and to simply do a complete reinstall?