Una spiegazione plausibile potrebbe essere questa: quando hai installato il programma X, synaptic ha provveduto anche ad installare tutta una serie di pacchetti che sono dipendenze di X (ovvero che servono al suo corretto funzionamento, ad esempio librerie ecc.). L'opzione Rimuovi completamente che hai utilizzato per disinstallare il programma serve a cancellare anche i suoi file di configurazione di sistema, ma i pacchetti precedentemente installati come dipendenze sono rimasti.
Per verificare se hai pacchetti non più necessari prova a dare da terminale il comando sudo apt-get autoremove e vedi se ti propone di rimuovere qualcosa.