Este é um conhecido bug :
- Atualize o VirtualBox pelo menos para 4.2.2 (a melhor maneira de fazer isso é adicionar o repositório oficial, consulte aqui sob distribuições baseadas no Debian)
- Configure o dns manualmente dentro da máquina virtual (você pode usar o 8.8.8.8, o Google, abrir o dns ou o seu servidor ISPs como o servidor dns de sua máquina virtual).