Tente editar os servidores DNS de dentro do NetwrokManager.
Primeira execução em um terminal
sudo rm /var/lib/apt/lists/* -vf
Em seguida, abra o NetworkManager e edite sua conexão atual, alterando as configurações de DNS. Vá para configurações do ipv4 e selecione Endereços automáticos (DHCP) apenas como método e escreva manualmente os servidores DNS que você deseja. Aqui estamos usando os servidores do Google OpenDNS 8.8.8.8 e 8.8.8.4, você pode adicionar vários endereços, separando-os com uma vírgula.
Em seguida, execute
sudo service network-manager restart
sudo apt-get update