Tem certeza de que o tráfego SMTP de entrada está chegando ao seu servidor? Muitos ISPs nos Estados Unidos bloqueiam esse tráfego.
Use o nmap ou o netcat para ver se sua máquina está acessível a partir das camadas internas: primeiro na lan, depois fora de seu firewall (por exemplo, uma conexão sem fio para seu gateway) e depois em um site remoto.
Quando você receber a mensagem de erro do Gmail, o erro real ajudará a diagnosticar o problema.