Isso provavelmente se deve ao uso de um proxy. Você pode verificar usando:
sudo apt-get -o Debug::Acquire::http=true update
Isso lhe dará uma visão retrospectiva. Você pode verificar seus arquivos de configuração para algum proxy configurado:
grep -i proxy /etc/apt/apt.conf.d/* /etc/apt/apt.conf
Se nenhum for encontrado, verifique suas configurações de rede na GUI e suas variáveis ambientais:
echo $http_proxy $HTTP_PROXY
Dependendo de onde você o encontrar, você deve desconfigurá-lo. Poderia haver também que os servidores estão em baixo, mas desde que você mudou de servidor é difícil isso acontecer.