O Postfix não pode se conectar aos servidores do Gmail por algum motivo. Isso pode ser devido a um problema de firewall ou roteamento. Tente executar o seguinte comando:
traceroute -T -p 25 <problematic server>
Isso deve lhe dizer exatamente onde o problema está localizado. É claro que, se o fizer somente enquanto o problema estiver acontecendo, talvez seja necessário tentar algumas vezes ...