Pode ser um caso de portas bloqueadas.
Qual é a saída de /var/log/mail.log
Se você estiver usando um firewall, talvez você deva verificar as regras considerando as portas em questão.
Para iptables, um sudo iptables -L
deve gerar as regras atuais. Se as portas estiverem fechadas, você poderá informar o iptables ao tráfego de entrada usando:
sudo iptables -A INPUT -p tcp --dport PORT_NUMBER_HERE -j ACCEPT
Para um tutorial completo sobre o iptables, verifique aqui
Também este é muito bom tutorial sobre como configurar um servidor de e-mail no Ubuntu 12.04 usando Postfix, Dovecot e MySQL para caixas de correio de usuários virtuais (testados pessoalmente no servidor de produção)