Какой дистрибутив используете? Какие репозитории подключены? Возможно, некоторые из них недоступны, поэтому менеджер обновлений считает, что информация об их содержимом устарела.
Я рекомендую использовать вместо "менеджера обновлений" стандартные команды
sudo aptitude update
sudo aptitude full-upgrade
или в крайнем случае обновляться через Synaptic. Постоянно висящий в памяти процесс, который к тому же работает не всегда корректно, мне кажется лишним в системе.