No hay necesidad de restaurar de fabrica.
Si eres Root, puedes usar este método.
-Descarga Root Explorer o cualquier explorador de archivos con permisos para borrar/modificar
-Después de instalarlo vete a /data/system/ y busca accounts.db
-Bórralo accounts.db
-Reinicia tu telefono.
-Arranca tu gmail o Google Play y veras que tienes que volver a configurar una cuenta de google ;) (Claro, si quieres)
Saludos.