reboot был лишним.
Вообще, линуксу, в отличие от винды, перегружаться требуется существенно реже. Отдельные сервисы, как правило, можно запустить или остановить не трогая остальной системы.
Здесь нужно было
sudo aptitude update
или
sudo apt-get update
Или Reload в синаптике.
Команды эквивалентны, но aptitude - более прогрессивный вариант, т.к. лучше разруливает зависимости между пакетами. Его же рекомендуют разработчики APT ( ==Advanced Packaging Tool != apt-get)
На хабрахабре недавно была статья по поводу того, почему aptitude лучше apt.
Единственное, чего нет в aptitude - поиска неустановленного пакета по имени файла (apt-file search).