После одного из внеплановых перезапусков сервера apt-get и aptitude начисто отказались работать, ругаясь на segmentation fault. Проверка диска с помощью fsck ничего не дала, но помогла следующая команда:

rm /var/cache/apt/*.bin

После этого всё заработало, как надо:)