My phone is (apparently) hijacked by a virus
While I do not know exactly what virus is causing this, it does appear that it has broken its way into the OS itself. A factory reset won't help you now. I would recommend you do not put any personal information on this device until you can clear out the virus.

At this point you have 2 options:


If the device is under warranty, see what the manufacturer will do for you. They will probably not help you, but it's worth a shot.
Flash the OS of the phone. This can be a risky procedure, but if done carefully and exactly as the tutorial you find for your device says you should be okay. Doing this also requires you to root the device, which will invalidate the warranty. At this point, you would flash a custom recovery and flash either the stock rom or an alternate rom such as cyanogenmod or paranoid Android. Look up tutorials on how to do this for your device.


Sorry to break the bad news.