The problem was in Debconf. See:
My frontend was, in fact, KDE.
1. Edit the config.dat file as in the bug report.
2. Run dpkg --audit
3. For each problem package run dpkg --configure <package>
Fix the half-configured ones first.
Thanks to all the people who offered advice - it led me in the right direction.