Softonic? No hombre no, no, huid de esas páginas que os instalan de todo menos lo que estáis buscando.

A ver, restaurando el teléfono a valores de fábrica debería funcionar... También puedes decirle cuando configures de cero que no restaure nada desde la cuenta de gmail que usas.

Yo he tenido varios androids y nunca me ha pasado eso. Supongo q no habrás instalado ninguna apk desde fuera del market.

Suerte.