Google Apps no responde incluso después de un restablecimiento de fábrica

Tengo un problema muy molesto con las Google Apps de mi teléfono, que no puedo resolver ni siquiera diagnosticar. Afecta a Google Play, Google Maps, Chrome, YouYube, los Ajustes de Google, la gestión de cuentas y probablemente otras apps. Todas ellas se congelan cuando intento acceder a ellas y al cabo de un rato aparece el mensaje "(App) no responde". Curiosamente, la aplicación de Google (el motor de búsqueda), la aplicación de Gmail y Google Translate funcionan correctamente.

Al principio, pensé que tenía un virus o que alguna nueva actualización había causado el problema, así que borré los datos de Google Play y reinicié el teléfono. Desgraciadamente, no sirvió de nada. A continuación, pensé que era un problema de conexión a Internet, sin embargo, otras aplicaciones que necesitan acceso a la web funcionan bien (por ejemplo, Evernote, Duolingo, un juego de carreras /Top Drives/ al que juego de vez en cuando, e incluso mi navegador secundario /UC Browser/). Por esta razón, tomé medidas drásticas y restablecí mi teléfono a su configuración de fábrica (sin restaurar ningún dato anterior). De nuevo, nada. Para colmo, mi batería empezó a agotarse más rápido de lo habitual y sospecho que los servicios de Google Play son la causa de ello. Cuando comprobé el historial de la batería, vi que incluso en el modo inactivo, Google Play está utilizando la CPU para algo.

Debo señalar que después de reiniciar el teléfono, introduje play.google.com desde mi otro navegador y me di cuenta de que el sitio seguía pensando que mis antiguas aplicaciones (las que tenía antes de formatear mi teléfono) seguían instaladas en mi dispositivo. Claramente, esto significa que Google Play y mi teléfono no se sincronizan correctamente.

A estas alturas, me he quedado a oscuras. No tengo ni idea de si el problema está relacionado con el software, el hardware o la autorización. Debo señalar que pedí prestado un viejo smartphone a un amigo mío y pude cargar una configuración funcional de Android en él con mi Gmail.

¿Alguien sabe cuál puede ser la causa de este problema o quién ha experimentado algo similar? Ya he leído todas las soluciones estándar que aparecen en el foro de soporte de Google y ninguna de ellas ha funcionado.

PS Mi teléfono es Lenovo P1 Vibe, menos de 2 años de edad. Mi versión de Android es la 5.1. La última vez que pude usar el teléfono normalmente fue hace 2 días, cuando vi un programa en Internet antes de ir a la cama. Me di cuenta del problema después de cargarlo a la mañana siguiente.