Починил. В лоб.
Запустил apt-get -s reinstall kde, система сообщила о паре пакетов с неудовлетворенными зависимостями.
Опять выполнил -s reinstall с одним из этих пакетов, опять получил кривые пакеты.
На очередной итерации система предложила удалить 4 пакета (из 5-го kde).
Выполнил живой реинстал с удалением, после чего переустановил кеды. Доставилась еще куча каких-то либов (уже без удалений), после чего система корректно (вроде) загрузилась.
