This usually is a result of the mail server requiring authentication.
If you are using Outlook 2003, here are the steps to enable authentication:
Open Outlook
Go to Tools | Email Accounts

"View or change existing e-mail accounts" should already be marked

Click Next
Select the Account with the trouble and click Change

Click on More Settings

Click on the Outgoing Server Tab
Click "My outgoing server (SMTP) requires authentication" and make sure "Use same settings as my incoming mail server" is selected

Click on the Advanced Tab
Set "Outgoing server (SMTP):" port to 26

Click OK and then Test Account Settings

If everything is fine and reports no errors,

Click Close.
Click Next.
Click Finish.
If an error does occur, it will switch to the Errors tab and display the error

If you are still having errors, make sure your login username is your full email address and that the password is correct.
If both of these are correct, please, do contact us and we'll investigate your issue further