A versão de apt-cacher em execução no host do proxy está desatualizada.
Veja link e link .
No meu caso, descobri que, como eu tinha modificado /etc/apt-cacher/apt-cacher.conf no meu host proxy, as atualizações regulares do apt [itude] não tinham atualizado apt-cacher.conf .
Eu encontrei apt-cacher.conf.dpkg-dist no mesmo diretório, usei o diff para determinar quais configurações eu precisava manter, então atualizei apt-cacher.conf .
Como estou atualizando para o Trusty, também o adicionei à lista "ubuntu_release_names" no mesmo arquivo, reiniciei apt-cacher e está tudo bem.
(Meu proxy está executando 12.10)