Начать с удаления пакетов из посторонних репозиториев.
apt-cache policy и смотреть на содержимое.
Частично можно чинить удаляя некритичные пакеты (например, браузеры и
т.д.), после починки можно поставить снова.
Логи того, как оно ломалось есть в /var/log/apt и в /var/log/dpkg.
Обычно, если сам apt жив, разрулить можно, хотя и геморрно.