Verifique seu /etc/resolv.conf
Pelo menos um dos ipaddrs "nameserver x.x.x.x" deve responder aos pings.
Se não houver, tente executar o ping 8.8.8.8
Se 8.8.8.8 as respostas, adicione-as ao resolv.conf:
echo nameserver 8.8.8.8 >> /etc/resolv.conf
Se não, verifique sua conexão com a Internet.
Verifique também suas fontes de APT:
grep -rv '^$' /etc/apt/sources.list* | grep -v ':#'
Podem ser inválidos e inacessíveis.