Alterado de comentário para resposta.
Verifique sua configuração de proxy para o apt em /etc/apt/apt.conf.d/ (talvez um arquivo chamado proxy ) ou /etc/apt/apt.conf .
Eu desabilitei todas as variáveis de ambiente de proxy e também alterei o proxy para None em Network Proxy. Apesar de fazer isso sempre que estou executando o sudo apt-get update ele tenta se conectar ao servidor proxy. Onde está o problema?