It sounds like your SMTP server requires user authentication before use. Make sure you have the correct mail settings setup. Especially take a look at the settings that are part of $_CONF['mail_settings'] in config.php:
'auth' => true,
'username' => 'smtp-username',
'password' => 'smtp-password'
-Vinny