Ok, finalmente consegui consertar. O problema foi uma terceira entrada de um "parceiro canônico - adicionado por software". Ele não estava no topo da lista, ao lado dos outros repositórios de parceiros, então eu não o reconheci. Para desativá-lo eu tive que usar o sudo, mas como ele não pediu uma senha eu tive que usar:
sudo software-properties-gtk
e digite minha senha. Então eu fui capaz de desativar. A atualização do sistema está funcionando novamente, também o apt-get em si e o preenchimento automático.