This means that there is a problem with your outgoing server aka the SMTP server. I went to the AT&T website and verified the settings that were there.
Normally when you are in the situation you are in – it is the outgoing servers authentication that is not checked:
Check the My outgoing server (SMTP) requires authentication checkbox. If the Incoming Mail Server (POP3) for the account being setup is your AT&T account (fpostoffice.isp.att.net) than: Choose Use same settings as my incoming mail server and click OK.
And of course make sure you are using an ATT internet line or this will always fail.