¿Usas otra o más tiendas que no sea la de Google? ¿Has instalado aplicaciones descargada de páginas web? ¿Aparte de la Play Store, tienes alguna otra aplicación (por ejemplo el navegador web) con permisos para instalar aplicaciones?
Intenta repasar lo que hayas hecho últimamente a ver si das con la fuente del problema. Es importante porque corres riesgo de que te pase otra vez y para ir descartando cosas como, por ejemplo, que se la hayan colado a Google en su tienda.