Você pode querer reinstalar o dpkg fazendo o seguinte:
sudo -i
mkdir /tmp/dpkg
cd /tmp/dpkg
Lembre-se de que você pode querer saber se os links de download ainda estão atualizados
Se você estiver executando uma versão de 32 bits do Ubuntu
wget http://security.ubuntu.com/ubuntu/pool/main/d/dpkg/dpkg_1.17.5ubuntu5.2_i386.deb
Para 64 bits
wget http://security.ubuntu.com/ubuntu/pool/main/d/dpkg/dpkg_1.17.5ubuntu5.7_amd64.deb
então
ar x dpkg*.deb data.tar.gz
tar xfvz data.tar.gz ./usr/bin/dpkg
Agora copie o binário para /usr/bin
com
sudo cp ./usr/bin/dpkg /usr/bin
E finalmente execute
sudo apt-get update
sudo apt-get install --reinstall dpkg