history |grep dpkg

al ejecutar ese comando me tira el siguiente resultado:

197 dpkg firefox_3.6-1_all.deb
225 /var/backups/dpkg.status.0
226 /var/backups/dpkg.0
228 /var/backups/dpkg.0
229 /var/backups/dpkg
244 history |grep dpkg

y la carpeta no la borre de un modo grafico sino que modifique los permisos con el chmod y la borre completa con el rm -r

por tanto no has usado rm para eliminarla, bien, sigamos jugando a las adivinanzas...

ls /usr/bin/dpkg /etc/dpkg /usr/lib/dpkg /usr/share/dpkg

> la borre completa con el rm -r

bueno, pues en ese caso

history |grep rm

al ejecutar eso me sale esto

/usr/bin/dpkg

/etc/dpkg:
dpkg.cfg origins shlibs.default shlibs.override

/usr/lib/dpkg:
methods mksplit parsechangelog

/usr/share/dpkg:
archtable cputable origins ostable triplettable

Todas las carpetas dpkg están en su sitio ... ¿que has borrado exactamente?

borre la carpeta dpkg que esta en /var/lib/dpkg

Empezáramos por ahí. Que cosas mas raras se os ocurren ... enfín

pues lo primero que yo haría sería intentar reinstalar el paquete dpkg a ver si va cubriendo los huecos, por supuesto tendras que hacerlo con la información de /var/lib/apt

veamos que pasa si haces

apt-get install -r dpkg

si dice que nones (que es fácil que lo diga) ya sabemos algo más

Para recuperar el listado de paquetes disponibles para ser consultado por dpkg podrías probar también dselect update, pero me da a mí que eso sí que no va a funcionar, no pierdes mucho por probar de todos modos, primero intenta lo de apt-get.

supongo que habrás querido decir apt-get install -f ya que apt-get install -r no hace nada

al ejecutar apt-get install -f dpkg me dice lo siguiente

E: No se pudo abrir el fichero de bloqueo '/var/lib/dpkg/lock' - open (2 No existe el fichero o el directorio)
E: Unable to lock the administration directory (/var/lib/dpkg/), are you root?

y digo yo... ¿porque no creas el dichoso directorio?

Fijate en este enlace

Quizás restaurando el archivo /var/lib/dpkg/status, puedas usar los demas comandos.