I had this problem with my earthlink e-mail. Eventually I figured out that the outgoing mail server used a specific port (587). After a lot of time with 3 or 4 different level 2 tech reps at Sprint, I found out you that when you enter the outgoing server you can also designate this port number by adding
ortnumber
In my case, it was smtpauth.earthlink.net:587
Hope this helps.