Apenas um palpite, mas talvez a MTU configurada no adaptador de rede VPS seja maior do que a rede realmente suporta. Talvez você queira tentar algo como:
ifconfig eth0 mtu 1500 up
eth0
, eth1
ou qualquer que seja a interface do seu VPS com a Internet. 1500 é a MTU padrão para redes Ethernet.