I encountered the following error in Aptitude after my Ubuntu 9.10 box fubar’d during an install. The message given by synaptic is similar.
Reading package lists… Error!
E: Encountered a section with no Package: header
E: Problem with MergeList /var/lib/dpkg/status
E: The package lists or status file could not be parsed or opened.
The following sequence of commands fixed it for me.
#: cd /var/lib/dpkg
#: sudo mv status status-bad
#: sudo cp status-old status
#: sudo apt-get update
Ended up having to do the same for /var/lib/dpkg/available and recovering the system.