Comment 2 for bug 1076260

I was able to determine that this was caused (in my case) by a mistake in my SSD optimizations of the filesystem. Certain parts of the /var tree were replaced with tmpfs filesystems and thus the contents were lost upon reboot. I missed /var/cache/debconf (I expect there is a whole flamewar that could go here about the appropriateness of configuration data being stored in /var).

I used the process from this thread on the ubuntu forums to rebuild my debconf database: http://ubuntuforums.org/showthread.php?t=1823695

After this, I was able to perform upgrades again.