I think you should ditch the provider email and go with a free one from Google, yahoo, etc. that way when you move or change providers you don't have to worry about it.
In regards to your issue, it could be what was previously suggested, or it could be that AT&T is blocking outgoing mail on port 25 (SMTP) which I've seen what some service providers use. Most of the free ones use some type of SSL which is a different port and more secure.