This can be caused if the email address desired is currently the same as any username on the record, the system is seeing the username field as an email field, and thinks a record already exists.

The solution is to temporarily change the username to something else, replace the email address to the desired one, and then change the username back, if desired.