The problem may be with relaying. If your "from" address in an email is from a different domain than the domain that receives your email (e.g. using xxx.mac.com to send emails and you have one that is "from" email@example.com) then the server may reject your email; they do that to block spam that uses a server's address.
If you check the settings for the outgoing Mail Server, primary server, be sure to enter the user name and password. These may be labeled as "optional", but enter them still.