Então tivemos que seguir um caminho completamente diferente e acabamos fazendo o seguinte:
Crie uma lista de versões de todos os pacotes instalados usando:
dpkg-query -W -f '${status} ${package} ${version}\n' | sed -n 's/^install ok installed //p' | sed 's/ /=/' | sort | tr -d ''
Obtenha as seleções usando:
debconf-get-selections | sed '/^#,*/d'
Faça o download de todos os debs usando:
cat "$package_list" | xargs apt-get download
Então, através do uso de:
dpkg-scanpackages
Conseguimos criar nosso próprio repositório local de pacotes, inserir esse repositório como o primeiro elemento na lista de fontes e apenas executar uma instalação apt com todas as versões corrigidas. Et Voila!