A conexão NAT precisava ser selecionada com o hardware sendo:
AMD PCNet FAST III (Am79C973, the default)
Isso funciona com praticamente qualquer SO (como mencionado na página de ajuda do Virtualbox ). A configuração da Intel, por algum motivo, não funcionou.
Para configurações de rede com configurações pesadas do roteador, talvez seja necessário usar a opção Ponte com "PCNet FAST III" como padrão.