O problema pode vir do seu arquivo /etc/resolv.conf, verifique se você tem algumas diretivas nameserver
sobre ele e tente executar o ping em archive.ubuntu.com
Aqui está o meu resolv.conf:
domain local
search local
nameserver 8.8.8.8
nameserver 8.8.4.4
Eu uso o DNS público do Google ( link )
Em seguida, tente o apt-get update