Have you checked against AT&T's instructions for setting up to use their
email servers? Such intructions are often written by someone better than
people who answer the phone for problems.
http://helpme.att.net/article.php?item=10918
Also, can you move the oldest message in your Outbox to the Drafts
folder, or delete it? If neither works, download and install this fix,
with Windows Mail not running:
http://support.microsoft.com/default.aspx/kb/941090
Although it's labelled as for messages stuck in the Outbox, it also works in
other folders. If you don't know whether to use the 32-bit version or the
64-bit version, try the 32-bit version first. Certain common antivirus
programs, such as most of those from Norton or McAfee, or a recent one
from Trend, tend to cause such problems, although seldom immediately,
so if you have such a program, remember where to find the fix - you are
likely to need it again.