dpkg-reconfigure -a не помогает? но это скорее всего будет долго
Да мне не важно, долго или нет, починить бы. До этого всю жизнь обновлял *BSD (фряху и опенку), никогда с зависимостями не было никаких проблем. С пингвином читал где-то, что бывает кривое обновление пакетов, всё ломается, надо ручками править. Так что первый опыт неудачный, к сожалению...