Если apt-get autoremove не помогает, вы можете запустить это (требуется aptitude, занимает очень много времени, как час! - не знаю, можно ли это сделать быстрее):
for i in $(dpkg -l | grep "^ii" | awk '{print $2}'); do aptitude why "$i"; done | grep "Unable to find"
В этом списке перечислены все пакеты, в которых aptitude не может найти причин, по которым они установлены (но вы, возможно, их установили вручную).