Based on Ian and Colin's comments, reassigning as a possible kernel bug to linux-source-2.6.15. ** Changed in: dpkg (Ubuntu) Sourcepackagename: dpkg => linux-source-2.6.15 -- maintainer of /var/lib/dpkg/alternatives/ doesn't do updates safely https://launchpad.net/bugs/37435