Bem, graças ao @cl-netbox e @Videonauth, resolvi o problema.
Aparentemente, mesmo que python-apt
esteja atualizado, algum outro pacote (que provavelmente depende) não foi, e essa foi a causa do problema.
Basta executar
sudo apt dist-upgrade
sudo reboot
Corrigido o problema.