Running
apt-get
from the command line wasn't much help either:
Fortunately, the fix was easy, as detailed in this Ubuntu Forums entry. Apparently this is caused by a corrupt APT cache.
To fix this problem, just delete the
*.bin
files from /var/cache/apt
.sudo rm /var/cache/apt/*.bin
That did the trick!