Provavelmente, é tarde demais, mas pode ser útil para alguns de vocês. Eu tive exatamente o mesmo problema, e percebi que uma das minhas variáveis de ambiente estava quebrada, levando exatamente ao mesmo problema.
Eu descobri digitando:
env | grep UTF
que me deu, se bem me lembro:
LANG=fr_FR.UTF-8
LANGUAGE=fr_FR.UTF-8 git
Então eu fiz:
export LANGUAGE=fr_FR
e eu pude continuar com o apt-get. [finalmente eu reinstalei toda a distribuição, mas pelo menos esse problema foi resolvido ...]