Ich würde ähnlich vorgehen wie der_bud, aber doch mit einigen korrekturen:
Grundsätzlich würde ich auch dpkg mit force optionen nutzen. Das ist unter normalen umständen quasi untersagt, weil dein system *garantiert* inkonsistent wird. Per definition wird damit *erzwungen* gegen regeln zu verstoßen die dazu da sind das system konsistent zu halten.
Wir tuen das hier dennoch, weil wir recht gut wissen was wir tun, dennoch ohne garantie. Wir wollen pakete, von denen *andere* pakete abhängen, löschen um sie durch pakete zu ersetzen, die (hoffentlich ;-) ) genau die gleichen rückwärtsabhängigkeiten besitzen. Am ende ist das system wieder konsistent, soll es zumindest sein.
Im gegensatz zu der_bud würde ich *auf keinen fall* remove verwenden, weil es konfigurationsfiles zurückläßt. Statt dessen würde ich "purge" verwenden was (ausser in deinem home, aber libraries werden dort kaum etwas hinterlassen) alle konfigfile eine pakets mitlöscht:
dpkg --force-depends --purge foo
Dann würde ich nicht apt verwenden, sondern würde, nachdem ich zuvor schon alle neuen ersatzpakete, notfalls per browser, heruntergeladen hätte - und es gibt hoffenlich zu jedem dmo paket ein entsprechendes Debian paket - alle pakete per
dpkg -i foo
installieren, und falls dies so nicht gehen sollte, was gut möglich wäre, dann installierst du die pakete mittels
dpkg -i --force-overwrite foo
Da am ende alle benötigten pakete wieder da sind ist dein system wieder konsistent.
Dann erst würde ich ein d-u hinterherschieben.
Ich will nicht behaupten das der_bud_s variante mit apt-get -f install nicht funktioniert, vielleicht kann auch das klappen, aber die remove option solltes du in jedem fall durch die purge option ersetzen. Der rest ist *vielleicht* ausprobierbar.