Je pense que autoremove a évolué.
Voici ma pratique : quand je le lance, il nettoie les noyaux en gardant les deux derniers, enfin, normalement : mon post du dessus disait que justement j'avais trouvé des 3.12 qui trainaient alors que mes 3.13 étaient bien nettoyés comme tu viens de le voir. (bien sur, il nettoie aussi les autres paquets devenus inutiles)
Par ailleurs, pour nettoyer les kernels "oubliés" j'utilise simplement
dpkg -l | grep linux-image- pour trouver les kernels de la bécane.
Puis également autoremove le-ou-les-kernel(s)-en-trop --> exemple que je fais pour toi :
:~$ sudo apt-get autoremove linux-image-3.13.0-16-generic
Lecture des listes de paquets... Fait
Construction de l'arbre des dépendances
Lecture des informations d'état... Fait
Les paquets suivants seront ENLEVÉS :
linux-image-3.13.0-16-generic linux-image-extra-3.13.0-16-generic
0 mis à jour, 0 nouvellement installés, 2 à enlever et 0 non mis à jour.
Après cette opération, 193 Mo d'espace disque seront libérés.
Souhaitez-vous continuer ? [O/n]