Ah seems like a conequence of the
This was really no good idea as all info about installed packages was lost. This also means that all files which belong to previously installed packages but not to their newer versions (if installed at all) are orphaned, making it impossible to clean this up. Do you still have the /var/lib/dpkg/status.old? And are there packages listed in /var/lib/dpkg/status.old which are not listed in /var/lib/dpkg/status?
diff <(grep '^Package:' /var/lib/dpkg/status.old) <(grep '^Package:' /var/lib/dpkg/status)