Hola a todos, yo he conseguido solucionarlo haciendo lo siguiente:
Dejar pulsado el botón Menú, el que está a la izquierda del Home, durante unos 3 segundos.
En la ventana de Búsqueda de Google empezar a escribir "ajustes" y aparece en la lista el icono de ajustes del teléfono
En ajustes, ir a Aplicaciones->Administrar aplicaciones->pestaña Todos
Bajar hasta encontrar TwLauncher, Forzar detención y borrar datos.
Ya está, los iconos del escritorio te salen como aparecen cuando has formateado el teléfono, porque te borra la personalización, pero no habremos tenido que formatear el teléfono ni borrar nada.
He de decir que antes de hacer esto había desinstalado las últimas aplicaciones que había instalado que podían ser sospechosas de haberme causado el problema, pero eso no me había funcionado. A lo mejor haciendo directamente esto de borrar datos del TwLauncher se arregla directamente sin tener que desinstalar nada. Ya me diréis.
Saludos!