Você provavelmente definiu as configurações de proxy globalmente, para que elas se aplicassem a todos os aplicativos, incluindo apt-get .
Quando você desativa as configurações de proxy, clique no botão que diz "Aplicar todo o sistema" (ou algo parecido). Ele solicitará sua senha. Agora você precisa reiniciar o Terminal para que as configurações sejam aplicadas.
Se isso não resolver o problema, veja se /etc/apt/apt.conf existe. Isso pode ser feito com:
cat /etc/apt/apt.conf
Se o arquivo existir (se você vir alguma saída), abra-o. Isso pode ser feito com:
gksudo gedit /etc/apt/apt.conf
Se o arquivo contiver uma linha com Acquire::http::Proxy , exclua a linha ou coloque um # na frente da linha. Salve o arquivo e saia do editor de texto.
Tente novamente o comando sudo apt-get .