Back in November, I had cause to update my password in Apple Mail on my iPhone,1 and ended up seeing a thoroughly inscrutable error: “Invalid Email Address”. Seeing as I had not changed the email address used for the account settings, only the password, this made absolutely no sense.
The problem, it turned out, was that I had aliases set up with which I can reply, because I have multiple domains that run through the same email account transparently. The solution was to remove all of the aliases and retain only the main email address for the account, confirm the password change, and then add back the aliases.
This is a terrible error message, and frankly a dumb design (I would just call it a bug, in fact!), But hopefully this explanation and work around will help someone else out there.