Your pop3 and smtp servers are mail.bellsouth.net and I believe that bellsouth requires smtp authentication. Did you try placing a check mark in the SSL authentication box in the treomail set up? I'm not sure if treo mail works with BellSouth, you might also try Eudora as I've read that others are able to send and retrieve bellsouth email with this email client as it supports authentication.
I downloaded EUDORA onto my TREO and have my e-mail working with Bellsouth it took all of 5 mintues. It took me four of them to navigate the Bellsouth site to find the POP mail settings. It is pretty slick, the only issue I have now is sending e-mail with the account.
I'll update when I have an answer.
I just got off a chat with good old Bell South and was told I could not send e-mail via the TREO through my Bell South account (only receive). The tech then went on to say that there were no plans to make the service availible that he knew of in the near future. Take this with a grain of salt as Bell South might give me another answer the next time I ask......