"an unknown error has occurred"or
"The package list needs to be rebuilt. This should have been done by the backend automatically"
E: Read error - read (5: Input/output error) E: The package lists or status file could not be parsed or opened.
Turns out it was a "simple" problem -- Kpackagekit and aptitude are both based on the Debian APT package. That package manager has a built-in limit as to the amount of cache space that it supports. If you exceed that limit (by having a bunch of repositories and packages stored on disk in /var), then APT and its descendents just give up. The error messages above are indicative of this kind of error (and certainly aren't very descriptive).
The problem is that - once you get to this point - you can't do much of anything. Attempts to run either command just fail.
Searching for KPackagekit info yielded nothing useful, but when I searched on aptitude and its error message, I found the solution: increase the cache limit.
Here's the source of this information. The fix is simple; just run this command and then you should be OK.
sudo apt-get update -o APT::Cache-Limit=25165824If you need, you can increase the Limit even further... it's only 24 megabytes which is nothing on today's systems.