Reading Code: man ucf makes me believe those files in /var/lib/ucf/ are not the cause, but a symptom. So I would debug APT and try to figure out how to get its database in sync with what is installed and removed. For example, can you find these 4:4:4: names in /var/lib/dpkg/* ? Sorry, I do not know how APT works so I'm only guessing where to look. You may have stumbled upon a bug, it may be worth reporting it to Debian. https://www.debian.org/Bugs/ I'm not sure which package to report this against, though. Try what Code: apt-get check reports and does.