Cuando vayas a hacer el reseteo de fábrica (no hace falta entrar en el Recovery) asegúrate de marcar la pestaña donde dice "borrar fotos, vídeos, contenido multimedia" o algo así. El móvil quedará sin ningún tipo de dato. Me da que es eso lo que te está fallando.