Aunque ha pasado un tiempo desde estos mensajes .. Por lo que (ahora) sé que Gmail por lo menos usa autentificación bajo SSL/TLS .. así que si usamos PHPMailer hay que hacerle algunos ajustes.
http://www.forosdelweb.com/f18/problema-con-php-mailer-409792/
El mensaje hace referencia a los problemas de conexión .. principalmente dados por uso de firewall's lo más probable por médio (o antivirus con esas funcionalidades).
Un saludo,