Usuário Lucid do Kubuntu aqui. Quando eu executo sudo apt-get update
eu não recebo uma lista de pacotes que precisam de atualização, eu acabei de obter a lista dos repositórios que estão sendo verificados. Por exemplo:
Get:1 http://packages.medibuntu.org lucid Release.gpg [197B]
Hit http://it.archive.ubuntu.com lucid Release.gpg
Hit http://archive.canonical.com lucid Release.gpg
Get:2 http://packages.medibuntu.org lucid Release [6854B]
(...)
sudo apt-get upgrade
me fornece a lista de pacotes que podem ser atualizados, se houver algum. Se o apt-get diz que não há pacotes atualizados, eu acho que você pode confiar nele, a menos que haja algum problema com o seu sources.list
... Mas então o apt-get update deve falar sobre eles.
A propósito, ultimamente eu tenho usado o aptitude ao invés do apt-get: eu acho melhor administrar problemas, me tirar de um canto apertado uma ou duas vezes ... Eu apenas faço:
sudo aptitude update
sudo aptitude safe-upgrade
Espero que isso ajude.