tienes que hacer wipe, ojo, si la formateas o particionas pierdes todo asi que haz los backups despues de particionarla. Con hacer el wipe que has puesto en el paso 7 te sirve, no hace falta que lo hagas varias veces.
luego puedes restaurar las aplicaciones, pero creo que ya no te aparecen como descargadas desde el market asi que no te avisa de actualizaciones ni nada.