Ciao Luca,
su mate e gnome2 c'e' un pacchetto che si chiama update-notifier ed e' il responsabile che ti fa apparire l'iconcina nella area di notifica utente. Prova a vedere se è aggiornato.
Non mi ricordo se la gnome3 utilizzi lo stesso pacchetto. L'ho disinstallata e quindi non riesco verificare.
Sull'output di aptitude non so risponderti (e' un comando che ho usato poco: guardero' la guida che ha indicato Samuel).
In ogni caso, se lanciando aptitude update esegue l'aggiornamento del repository (lista pacchetti disponibili) al pari di apt-get update