Por ahora lo he solucionado desinstalando todas las app que no venían de fábrica y volviéndolas a instalar. En cuanto a los contactos he metido un backup que tenía de hace unos meses.
A ver si no vuelve a pasar porque si fuera así es un fallo muy gordo!