Zen Cart is only REPORTING the problem to you. It is using the same settings it always had before when it was working just fine, right? So, logical deduction suggests that the problem is with something BETWEEN Zen Cart and the email service you're connecting to.
"Cannot connect to host" means that Zen Cart is using the information YOU supplied to it to try to login to the mail server and send mail. But the mailserver is either not responding, or the webserver has lost its ability to find the destination mailserver (nameserver lookup problem) and thus Zen Cart cannot connect because the server that Zen Cart is sitting on doesn't know what to do.
I can't see how or why this "sudden" problem would be a Zen Cart problem. You said yourself that the problem "suddenly" started after it was working fine. So, something outside of Zen Cart is what changed. You'll need to sort out what that is and have whoever is in control of that fix whatever they've broken.
.
Zen Cart - putting the dream of business ownership within reach of anyone!
Donate to: DrByte directly or to the Zen Cart team as a whole
Remember: Any code suggestions you see here are merely suggestions. You assume full responsibility for your use of any such suggestions, including any impact ANY alterations you make to your site may have on your PCI compliance.
Furthermore, any advice you see here about PCI matters is merely an opinion, and should not be relied upon as "official". Official PCI information should be obtained from the PCI Security Council directly or from one of their authorized Assessors.