Finalmente encontrei a resposta, acabou postfix estava tentando se conectar ao Gmail usando ipv6. Para corrigir isso, configure o ipv6 no servidor ou, como fiz, desative o ipv6 em /etc/postfix/main.cf
, adicionando a seguinte linha:
inet_protocols = ipv4
e reiniciando o postfix:
service postfix restart