I have a new Galaxy S4 and couldn't set up one of my email accounts, and kept getting "Authentication failed."
It turns out that the auto-populated fields make a mistake. It only populated "username" in the name box, instead of email@example.com
. Once I put in the entire email address, it worked like a charm.