Pessoal talvez alguns saibam o que vou falar aqui, mas aos que não souberem ou tiverem dúvidas fica a dica. Tenho usado o Kubuntu 8.10 e notei algo interessante na sua atualização, não sei se o mesmo ocorre no Ubuntu com Gnome.
O KDE indica sempre que há atualizações carregando o Adept na área de notificação. Aconteceu comigo dele indicar 8 atualizações, sendo que eu preferi atualizar via apt-get. Usei o apt-get primeiro com update e depois upgrade mas, pra minha surpreza, nenhuma atualização foi encontrada assim. Resolvi pesquisar e descobri duas formas de atualizar o sistema via linha de comando pegando aquelas atualizações, uma via apt-get e outra com aptitude.
sudo apt-get dist-upgrade
ou
sudo aptitude full-upgrade
Usando um desses comandos não haverá mais problema.