FIXED FOR ME ! I had 4 centurylink mail accounts (@q.com) on new 5s (set up by restoring from my 4s which was working fine) and getting the same as everyone. Called Verizon, who called Apple and Centurylink. No help from any of those.
I set up a new account for one of my gmail accounts (never on my iphone before) and it had no problem.
FINALLY (READ TO THE END) after reading all of this thread, on one account, I turned off the SSL and verified the port as suggested earlier. When I did, and clicked done, it told me my password was wrong, so I typed it in, hit done, and it verified and all was good. Mail could be sent out on that account. Same steps and password warning on the next account. So I got curious and went to a third account and only erased the User Name and retyped it in and typed in the password and BINGO, it worked as well. I did not have to touch the SSL setting (which was on). So I got more curious and went back to the first account that I had gotten to work and turned SSL back on, hit done (dont forget that little step at the top of the screen) it verified and all was still working, it didnt matter whether SSL was on or not. So far it appears that you just need to go to settings, mail,contacts,calendars, select your account,Outgoing Mail Server, SMTP, then probably Primary Server, erase and re-enter the User Name and Password. You have to hit done, and while backing out there will be another place to hit Done. Missing both of those "Done's" might have been a stumbling block for some of you earlier. Maybe when the info got picked up during the IOS upgrade or whatever, a binary letter got swapped and still looked the same on screen, but was sending a wrong character to the server. Whether or not that is true, this worked on the rest of my accounts. hope it does on yours!