Por lo que he visto no es tan sencillo e implica muchos borrados en el dispositivo. No dudo de que pueda hacerse de otra forma, más quirúrgica o más suave, pero si has tomado la decisión  es mejor no andarse con tontadas.

Según esta entrada de stackexchange se necesita ser root en el dispositivo y realizar los siguientes pasos desde el modo recuperación:

• Realizar borrado de fábrica
• Borrar el caché del sistema y el caché de Dalvik.
• Formatear la partición de sistema.
• Reinstalar la ROM (discutible pero ya puestos …)

Y funciona (pero sigue siendo drástico),