Я обнаружил, что «сломанные» пакеты вызывают проблемы с обновлением. Мои пакеты (gnuplot) не были явно разбиты (проверены при просмотре в диспетчере пакетов Synaptic), но были отмечены как не обновленные. Этот тип пакета также приведет к сбою обновления; их можно найти в диспетчере пакетов Synaptic, выбрав «Установленный (обновляемый)». Я просто пометил их для удаления, затем побежал
sudo apt-get dist-upgrade
sudo do-release-upgrade
... пока все хорошо!