Seria mais fácil solucionar seu problema se você postar os resultados obtidos ao tentar fazer ping em um endereço externo (como os servidores DNS do Google que você está usando), as configurações de rede atuais e sua tabela de roteamento.
/sbin/ifconfig -a
/sbin/route -n
Sem saber mais, isso é meio que um tiro no escuro, mas meus palpites são: a) você não está obtendo um endereço DHCP em eth0, ou b) suas configurações de gateway para eth1 estão mexendo com a rota padrão DHCP atribuído.
Se você não está obtendo um endereço DHCP para eth0, é provavelmente uma configuração incorreta no VirtualBox (como recuperar seus adaptadores).
De qualquer maneira, você não precisa de um gateway ou configurações de DNS designadas especificamente para eth1, já que isso será atribuído pelo DHCP em eth0, então eu removerei as linhas gateway, dns-search e dns-nameservers da sua configuração. Suas máquinas virtuais ainda poderão se comunicar sem uma configuração de gateway se estiverem na mesma rede e o VirtualBox estiver configurado corretamente.
Editar: Para garantir que você não tenha um gateway na eth1 após a reinicialização, remova as linhas do seu bloco eth1 para que fique assim:
auto eth1
iface eth1 inet static
address 192.168.56.1
netmask 255.255.255.0
Quando estiver pronto, você não terá nenhuma linha de gateway no arquivo de interfaces.