[ CONSULTA ] Error "Búsqueda de Google se ha detenido"

Hola, lo primero de todo si está esto fuera de sitio, perdonadme que es la primera vez que posteo.

Tengo un Nexus 4 con Android 4.4.2 rooteado y desde ayer me sale un mensaje con Google Now que dice : "La aplicación Búsqueda de Google se ha detenido", con lo que se imposibilita su uso.

He probado a borrar la caché y datos de las aplicaciones y hacerle un wipe/factory reset, wipe caché partition y wipe dalvik.
(Ya que le hice esto aproveché y le puse el CyanogenMod 11; después de comprobar que seguía sin funcionar con la ROM de Google)

Y nada, sigue igual, si desinstalo las actualizaciones funciona, pero claro está desactualizado. Y en el momento actualizo a la última versión de Búsqueda de Google y la abro me sale el mensaje otra vez.

Alguna ayuda por favor.

[Eskorbutin]

Probaste a flashear las PAGapps stock? A mi con las gapps de paranoid no me da ningun fallo

Sí y sigue sin funcionar. De hecho ahora en un acto de desesperación desde el recovery he hecho format/wipe a todo y el cyanogenmod no pasa de la pantalla de inicio u.u