SMTP Verification failed
My comment above notwithstanding, there is a possibility that this isn't a mail server issue.

If you recently upgraded to a newer version of PHP, you may have gone from a version that uses mcrypt to encrypt the outgoing mail password to one that doesn't.  To fix this, go to Administer menu » System Settings » Outbound Mail and re-enter your SMTP password and save.