So, I saw that there were some updates, and proceeded to do everything from the shell:

apt-get update
apt-get upgrade
apt-get autoremove

Happy that everything “just works” (so far), I confidently restarted the machine… Only to find I could not SSH back into, ping, or otherwise see my server…

Using the console (i.e. locally attached KVM), I found out I was now a “victim” of this. Although the errors were different, the “fix” was the same:

dpkg --configure -a
apt-get dist-upgrade
apt-get -f install
apt-get update

As per the post linked to above, YMMV.