Consegui trabalhar principalmente com o problema mantendo todos os pacotes que já estavam instalados no sistema.
Eu usei a seguinte receita:
dpkg --get-selections | grep "\binstall$" | sed s/install/hold/ > toHold.txt
dpkg --set-selections < selections.txt
dpkg --set-selections < toHold.txt
apt-get dselect-upgrade
Neste ponto, apenas um pacote, libxml2-dev: i386 ainda estava causando problemas, então eu o removi manualmente com:
echo libxml2-dev:i386 hold | dpkg --set-selections
apt-get install -f