A questão era que, de alguma forma, algumas das atualizações estavam corrompidas e não foram concluídas (ou similares, não tenho certeza do que aconteceu ou por quê).
Para corrigir, execute o seguinte:
sudo apt-get install -f
sudo dpkg --configure -a
sudo apt-get install -f
e, em seguida, reinicie.