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
3. Make sure your outgoing mail server IP address isn't on any of the global block lists (http://www.mxtoolbox.com/blacklists.aspx
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.