As long as you are certain you have followed the instructions for setting up your e-mail client to sendmail, including enabling SMTP Authentication, the only other possibility would be a problem with your ISP.
Most ISP's block sendmail’s default port 25. They do this so they can "control" your email habits (this is mainly geared to abusers or spammers).
Eugene Hosting has created an easy work-around to this problem. We have enabled SMTP on port 26, also. Change your email client SMTP port to 26. If this is the cause of your problem, then it should now work.