Eu encontrei uma solução que funcionou para um usuário com um problema relacionado ...
sudo -i
mkdir /tmp/dpkg
cd /tmp/dpkg
#i386 version
wget https://launchpad.net/ubuntu/+archive/primary/+files/dpkg_1.18.4ubuntu1.1_i386.deb
or
#amd64 version
wget https://launchpad.net/ubuntu/+archive/primary/+files/dpkg_1.18.4ubuntu1.1_amd64.deb
tar x dpkg*.deb data.tar.gz
tar xfvz data.tar.gz ./usr/bin/dpkg
sudo cp ./usr/bin/dpkg /usr/bin/
sudo apt-get update
sudo apt-get install --reinstall dpkg