Is alltel.net your isp and is mail.alltel.net the smtp server?
I noticed that in your line for relayhost, you have relayhost=mail.alltel.net. Change that to relayhost = mail.alltel.net then restart postfix. If that doesn't fix the problem, try the following.
Make sure you back up your /etc/postfix/main.cf file before attempting this.
This is the SMTP-AUTH clear text method:
Postfix needs to know how to behave as a SASL client. Add the following lines anywhere you'd like in your /etc/postfix/main.cf
relayhost = mail.alltel.net
smtp_sasl_auth_enable = yes
smtp_sasl_password_maps = hash:/etc/postfix/sasl_passwd
If you already have those lines, then you're set, if not, add them. Make sure you don't have any duplicates.
Create a file called /etc/postfix/sasl_passwd and add the following, using the syntax provided:
The host portion above must match what you used in the "relayhost" line in main.cf. Something as follows:
mail.alltel.net myid:mypw (your userid and password)
Save the file.
Hash the file.
[firstname.lastname@example.org] postmap /etc/postfix/sasl_passwd
[email@example.com] /etc/init.d/postfix restart