Muchas veces, borrar la caché desde el Recovery suele ayudar (y si esto no funciona, borrar también la Dalvik caché, o en el peor de los casos, hacer un factory reset, aunque con esto perderás todos los datos, configuraciones y programas instalados).
¿Lo has probado?