Поиск способа устранения проблемы нужно начинать с определения причины её возникновения. А значит вам нужно написать какие действия вы сделали перед возникновением проблемы.

Да, собственно, ничего особенного не делал в плане управления пакетами. Единственное, что ОС несколько дней назад восстанавливалась из резервной копии, которая создавалась через dd. Весь остальной софт работает нормально.

которая создавалась через dd

Подозреваю, что восстановилась не очень удачно. Какие-то файлы вполне могли повредится. Особенно если на диске есть битые сектора.

Problem with MergeList /var/lib/dpkg/status

Глянь в /var/backups. Там резервные копии /var/lib/dpkg/status есть.

Да, и расскажи, что получилось. Тогда дальше будем думать.

Целостность пакетов можешь проверить debsums -s. Но вот если она у тебя не стоит, то лучше ее отдельно скачай и поставь, раз у тебя apt не работает. Тебе выдаст список пакетов, у которых не сопадает или отсутсвует контрольная сумма. Этим пакетам сделай aptitude reinstall <список пакетов> или apt-get install --reinstall <список пакетов>. Сперва просто посмотри, нет ли там каких-то важных библиотек для apt.

удалять файлы из /var/lib/apt/lists

apt-get update или aptitude update делал после этого?

Глянь в /var/backups. Там резервные копии /var/lib/dpkg/status есть.

К сожалению, резервной копии status в этом каталоге у меня нет.

apt-get update или aptitude update делал после этого?

Делал, та же самая ошибка вываливается.

Оффтоп

Прочитал заголовок, аж слезы навернулись.

Вчера, четырьмя выстрелами в упор, в Нью-Йорке, был убит Джон Оно Леннон. Примерно так прочитал...

К сожалению, резервной копии status в этом каталоге у меня нет.

Она там dpkg.status.0 зовется.

Умерла :(

Она там dpkg.status.0 зовется.

Действительно, недоглядел. Восстановил dpkg.status.0, но проблема осталась, затем восстановил более старую версию dpkg.status.1.gz и пациент ожил.

С-П-А-С-И-Б-О.