Как уже писалось ранее, ступор и стерику у apt вызывал пакет openjdk-6-jre-headless. В смысле, данный пакет в репозиториях битый, при чем абсолютно одинаков на всех зеркалах.
Казалось бы, в чем проблема? Можно собрать из исходников! Не тут-то было. Попытка скачать исходники... повисла на 99%, как и с самим пакетом.

Долгие пляски с бубном и обещние с мануалами в онлайне сообщило, что пакет сей связан с запуском джава-приложений в гуе. Которых у меня отродясь не было. Следовательно, пакет можно принести в жертву суровый красноглазым богам.

Однако ждала меня подстава: пакеты удаляться не желали, а желали быть переустановленными. Что в итоге помогло - не знаю. Но могу предполагать.

1. Удалить IcedTea и Cacao

sudo apt-get remove --purge -y openjdk-6-jre
sudo apt-get remove --purge -y openjdk*
sudo apt-get autoremove