Can't connect to the Internet from VPS

Hi all
My VPS all of a sudden has lost connection to the Internet. Not sure what happened. I logged in one day because I noticed some backups to an external location were not happening, and even though I can reach it fine, SSH into it, etc, I can't ping any IPs on the Internet.

For example:
vps@vps:~$ ping 8.8.8.8
PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.
^C

It seems to stop here:

vps@vps:~$ traceroute 8.8.8.8
traceroute to 8.8.8.8 (8.8.8.8), 30 hops max, 60 byte packets
1 _gateway (51.89.148.1) 0.364 ms 0.323 ms 0.308 ms
2 192.168.143.254 (192.168.143.254) 0.294 ms 0.279 ms 0.265 ms
3 10.13.159.126 (10.13.159.126) 0.252 ms 0.270 ms 0.300 ms
4 10.13.158.136 (10.13.158.136) 0.281 ms 10.13.158.138 (10.13.158.138) 0.259 ms 10.13.158.136 (10.13.158.136) 0.224 ms
5 10.13.152.110 (10.13.152.110) 0.216 ms 10.13.152.114 (10.13.152.114) 0.224 ms 10.13.152.112 (10.13.152.112) 0.195 ms
6 10.72.4.112 (10.72.4.112) 0.468 ms 10.72.4.126 (10.72.4.126) 0.685 ms 10.72.4.118 (10.72.4.118) 0.771 ms
7 10.73.32.58 (10.73.32.58) 0.175 ms 10.73.32.56 (10.73.32.56) 0.169 ms 10.73.32.60 (10.73.32.60) 0.163 ms
8 * * *
9 be103.lon-thw-sbb1-nc5.uk.eu (213.186.32.252) 1.103 ms 1.114 ms be103.lon-drch-sbb1-nc5.uk.eu (91.121.215.118) 1.111 ms
10 * * *

Anyone have any ideas what might be going wrong?