Вчера была такая же проблема... Переставил быстренько корень системы и обновился - всё заработало. Но надо будет сегодня после работы проверить, потому что теперь понимаю, что не мой глюк и не я напортачил с репами.
И, видимо, глюк может повторяться.
Симптомы такие:
На sudo aptitude update выдаёт подписи к половине реп "игнор", очень медленно обновляет и грузит индексы, большая часть реп подписана "в кеше". Через gui видим, что часть реп (все сторонние репы) при загрузке подписаны "неудачно", а все остальные подписаны "совпадение". Хотя раньше везде было "готово" и грузилось в разы быстрее. В репах совершенно точно лежат новые пакеты на обновление, а ставятся старые версии из оф. репов.
Ума не приложу, что это за глюк и как решить.
Поступил ламерски, переставил систему.
Пока не проверял обновки после обновления ядра.