dpkg exit with error parsing file `/var/lib/dpkg/status`, what to do?

Lucky you! You have backups! And even more, they are made daily without you knowing! So, to restore the files just run:

sudo rm /var/lib/dpkg/status
sudo cp /var/backups/dpkg.status.0 /var/lib/dpkg/status
sudo apt-get update

Done!

If you need even older files there are more to choose from:

ls /var/backups/dpkg.status*
/var/backups/dpkg.status.0     /var/backups/dpkg.status.4.gz
/var/backups/dpkg.status.1.gz  /var/backups/dpkg.status.5.gz
/var/backups/dpkg.status.2.gz  /var/backups/dpkg.status.6.gz
/var/backups/dpkg.status.3.gz

Just uncompress them using gunzip:

gunzip -c /var/backups/dpkg.status.6.gz > /var/lib/dpkg/status

If the backups are no good, another way is doing a list of the doc directory contents:

sudo -i
ls /usr/share/doc | \
      grep -v [A-Z] | \
      grep -v '^texmf$' | \
      grep -v '^debian$' | \
      awk '{print $1 " install"}' | \
      dpkg --set-selections

http://www.debianhelp.co.uk/debianproblem.htm