Verifique se faltam algumas bibliotecas para o dpkg:
ldd /usr/bin/dpkg
Se alguma biblioteca estiver faltando, tente instalá-la. Se esse não for o problema, tente o seguinte:
sudo -i
mkdir /tmp/dpkg
cd /tmp/dpkg
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.2_amd64.deb
ar 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