Post the full SMTP error message.
Things to start off with:
1. Make sure your outgoing mail server IP address has a valid reverse DNS entry.
2. Make sure your outgoing mail server isn't an open relay (
http://www.abuse.net/relay.html to check)
3. Make sure your outgoing mail server IP address isn't on any of the global block lists (
http://www.mxtoolbox.com/blacklists.aspx to check).
4. Make sure you have SPF and Domainkeys set up (this may or may not be 100% necessary but good to have anyway).
There are probably other tips but those are the ones that come to my mind.