If you receive this error then it means that your mail server is unable to connect to your smtp provider most probably due to firewall. So check your firewall and if your server is listening to port 25, 587 and 465 which are the smtp ports unless you have specified some custom port no.
# netstat -ntlp | grep sendmail tcp 0 0.0.0.0:587 0.0.0.0:* LISTEN 1419/sendmail tcp 0 0 0.0.0.0:465 0.0.0.0:* LISTEN 1419/sendmail tcp 0 0 0.0.0.0:25 0.0.0.0:* LISTEN 1419/sendmail
Many a times it happens that your network firewall might be blocking some particular port so you can check using telnet.
DAEMON_OPTIONS(`Port=submission, Name=MSA, M=Ea')dnl
and for port 465 uncomment below line
DAEMON_OPTIONS(`Port=smtps, Name=TLSMTA, M=s')dnl
You can use ssl ports by adding these two lines in your sendmail.mc file
define(`RELAY_MAILER_ARGS', `TCP $h 587')dnl
define(`ESMTP_MAILER_ARGS', `TCP $h 465')dnl Save and exit your file
# m4 sendmail.mc > sendmail.cf
# service sendmail restart
For my configuration file you can refer this post
Now re-try to connect your SMTP server as in my case it is smtp.gmail.com using port no.
# telnet smtp.gmail.com 25 Trying 126.96.36.199... Connected to smtp.gmail.com. Escape character is '^]'. 220 mx.google.com ESMTP io2sm27316728pbc.24
So it shows connected, similarly you can check for other port no.