Você deve conseguir gerar o diretório usando algo assim:
for i in $(dpkg -l|awk '/^ii/ {print $2}')
do
apt-get --reinstall -y install $i
done
O que esse snippet deve fazer é reinstalar todos os pacotes que você já instalou. Também atualizará tudo. Se você não quiser fazer isso, terá que estender o script para instalar a versão específica que você instalou atualmente, o que não é garantido que funcione, já que esses pacotes podem não existir mais no repositório.
Mais informações e uma abordagem ligeiramente diferente: link
EDITAR: Dica importante do artigo relacionado acima:
Some packages will still not install correctly as more stuff is missing from /var/lib/dpkg. In particular the package "ucf" is important to enable the kernel and possibly some others to install correctly.
Without /var/lib/dpkg/info/ucf.templates the kernel install produces this error:
failed to install/upgrade: User postinst hook script [/sbin/update-grub] exited with value 10
Install ucf:
apt-get --reinstall install ucf
Esse artigo descreve a recuperação da exclusão completa de todos de /var/lib/dpkg
, portanto, essa etapa extra pode não se aplicar à sua situação.