I was able to work around the problem this bug cause by running: sudo apt-get install --reinstall debtags
See: https://bugs.launchpad.net/distros/ubuntu/+source/libapt- front/+bug/64531 -- [Dapper] Debtags https://launchpad.net/bugs/26007 -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs