A relay access denial usually means you're not authenticating to the server or you're using port 25 for your mail client (and avoid that), or that the server isn't authenticating correctly to the relay server, if you're using one of those.
Is this the same mail server that has had occasional issues before? (Here and here and here are some earlier discussions.)
Launch Terminal.app from Applications > Utilities and post the output of the following
sudo changeip -checkhostname
That should report no changes required.
Might also want to post the output of your postconf configuration. (I think postconf -n will still work on 10.8; the configuration files moved in 10.9, and the default postconf -n doesn't show the local configuration there.)
if you're still at that same domain, then there's also no public reverse DNS for the mail server from the ISP, which means mail that isn't being relayed can end up getting dropped by receiving mail servers:
$ dig +short MX pints.com.
0 mail.pints.com.
$ dig +short mail.pints.com.
69.196.158.234
$ dig +short -x 69.196.158.234
$