Esto puede ser por diversas razones, sin embargo la mas común se debe a que le falta activar la casilla de autenticación en su cliente de correo (Outlook, Thunderbird, Entourage,etc)
Por ejemplo desde Outlook 2003:
Dentro de la ventana de cuentas de correo se encuentra un botón que dice "Mas configuraciones" damos un click, y nos vamos a la pestaña de "Servidor de salida", debemos de tener activada la casilla que dice "Mi servidor de salida (SMTP) requiere autenticación" y seleccionamos la opción "Utilizar la misma configuración que mi servidor de entrada", damos click en el botón de aceptar y salimos de la configuración de correo.
Teniendo esta casilla de autenticación activada se debería de corregir su problema.