Le soucis, c'est des dépendances du type :
bli
bla
toto
plouf
libtrucnaze
trucnaze
Quand tu te dis que trucnaze c'est naze et que tu le désintalles avec apt-get, ça n'enlève que trucnaze.
Après deborphan va te dire que libtrucnaze ne sert à rien, mais pas plouf (ni les autres), vu que libtrucnaze est encore installé. Peut-être qu'avec une option bien choisie, deborphan donne un meilleur résultat. Vas voir le man 