OK, achei a etapa perdida graças a postagem .
Esqueci de definir a configuração listen_addresses no postgresql.conf. Estou usando esse valor, mas pode ser mais restrito:
listen_addresses = '*'
Só para esclarecer, quando você se conectar ao PostgreSQL a partir do host, use localhost como o servidor e 5432 como a porta. O VirtualBox encaminhará essa porta para o convidado.
Eu também percebi que algumas configurações exigem que você reinicie o PostgreSQL em vez de apenas recarregá-lo. O comando é:
sudo /etc/init.d/postgresql-8.4 restart