It might help with more specifics: are you popping/exchange etc???
Are you able to telnet to the smtp server from the backup exec server? if you are unable to telnet then most likely problem is that port 25 is blocked.
telnet command help:
http://support.microsoft.com/kb/153119
Make sure the server name is listed in dns and use the full name of the server - servername.domain.xxx
Also, is relaying allowed on the smtp server for the backup server?
Does your SMTP server require authentication ???