Using gmail as email relay for sendmail

I used to be able to send emails using a gmail account & sendmail configured using one of the guides on the Internet, for example: http://appgirl.net/blog/configuring-sendmail-to-relay-through-gmail-smtp/

This is a small server and I've recently moved it to a different house. And sendmail has stop working. The only thing different in the network setup is a new router.

What is happening:

1. In the log files, I see the following error:

   …stat=Deferred: smtp.gmail.com: No route to host

2. When I run from the command line:

   strace sendmail -f A -t B -u "Subject" -m "Message" -tls=yes ssl=yes -s smtp.gmail.com:587 -xu A -xp XYZ

It hangs on this call:

recvfrom(3, "m0\201\203\0\1\0\0\0\0\0\0\4ares\3lan\0\0\34\0\1", 8192, 0, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("192.168.1.254")}, [16]) = 26
close(3)                                = 0
time(NULL)                              = 1339997943
open("/etc/localtime", O_RDONLY)        = 3
fstat64(3, {st_mode=S_IFREG|0644, st_size=3477, ...}) = 0
fstat64(3, {st_mode=S_IFREG|0644, st_size=3477, ...}) = 0
mmap2(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xb76ff000
read(3, "TZif2\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\4\0\0\0\4\0\0\0\0"..., 4096) = 3477
_llseek(3, -24, [3453], SEEK_CUR)       = 0
read(3, "\nEST5EDT,M3.2.0,M11.1.0\n", 4096) = 24
close(3)                                = 0
munmap(0xb76ff000, 4096)                = 0
socket(PF_FILE, SOCK_DGRAM|SOCK_CLOEXEC, 0) = 3
connect(3, {sa_family=AF_FILE, path="/dev/log"}, 110) = 0
send(3, "<18>Jun 18 01:39:03 sendmail[268"..., 96, MSG_NOSIGNAL) = 96
nanosleep({60, 0}, 

So it looks like at some point it tries to resolve the DNS name, but I don't have anything running on 53, so it dies out and then just hangs. The other interesting thing is that msmtp works just fine on the same server.

Update: ares in strace output is actually the name of my server, but .254 IP address is the address of the router.

Could anyone tell me why this is happening or what further steps can I take to investigate the issue? Thanks!