Me he encontrado varias veces con ese problema, lo único que funciona de maravilla es:
Con un explorador con acceso root ( te recomiendo root explorer), borrar el fichero:
/data/system/accounts.db
Reinicias, y mano de santo, el teléfono no tiene ninguna cuenta. Ponle la que quieras.
La de pruebas que hice con esto hasta que dí con la tecla adecuada... Suerte.
Por si acaso... nunca está de más hacer una copia del fichero antes de borrarlo.
