This usually happens because the nameservers on the affected domain have been changed to make the domain work with our servers, but the domain itself has not been transferred in. There is a brief period when some remote mail servers direct mail according to the new MX records, but the local mailserver is still seeing the old MX records. This causes the mail server to reject mail until the old records expire. That usually happens within 24 hours. Domains which are fully transferred by-pass the MX record lookup and so are not affected by this problem.
This error could also be because you have not selected "My Outgoing Server Requires Authentication", or some variation on that depending on the email client software being used, in your settings. You can select it to use the same settings as the incoming mail server.
If you continue to receive this error after 24 hours (allowing for nameserver updates and DNS propagation), please contact Support.