Вот с такой проблемой недавно я столкнулся на своем домашнем компьютере с Ubuntu 12.04 LTS
Попытался обновиться через терминал, тоже не чего не помогло.
Решение достаточно простое.
Чистим компьютер от мусора на всякий случай.
$ sudo apt-get autoremove
Обновляем репозитории
$ sudo apt-get update
Пытаемся обновится
$ sudo apt-get upgrade
Получаем на выходе приблизительно то что и у меня.
Далее что бы обновить эти все пакеты которые не обновляются.
Нужно скопировать имя этого пакета, и установить заново:
$ sudo apt-get install имя_пакета
Или сделать:
sudo apt-get do-release-upgrade
sudo do-release-upgrade
Но мне систему обновлять не нужно, у меня 12.04)