Во, это другой вопрос. Тут уже понятно, что что то могло тупо не установиться, а информация об установке остаться. Ну лечение одно, для начала чистим все кэши (хотя тут дело, думаю, не в этом), затем долго и упорно разбираемся, куда же apt-get записывает информацию об установленных пакетах и чистим там, а затем узнаем о таком прекрасном механизме как aptitute, но уже поздно )