Abra dois terminais na sua VM, eles podem ser duas sessões ssh. Em um deles, emite como sudo
os seguintes comandos
apt-get update
apt-get install tcpdump
tcpdump -i eth0 -n icmp
No outro terminal, o usual
ping -c3 8.8.8.8
No primeiro terminal você deve ver os três pings, se não for sua culpa, caso contrário, você deve ver apenas um.
Isso aumentará suas chances de diagnosticar esse problema.
Editar:
Depois do que você disse na sua resposta, você deve instalar o mtr
e dar o comando
mtr 8.8.8.8
você verá onde os pacotes de ping são descartados.