O apt-get foi configurado para usar um proxy, usando um arquivo apt.conf
Esse proxy não está mais em uso, então o apt não estava sendo capaz de usá-lo.
O www funcionou, pois tinha sua própria configuração de proxy (sem proxy), através de Network- > Proxy de rede