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