Заметил ошибку в инструкции (для Ubuntu 9.04) на которую ты ссылаешься в первом сообщении, там две команды без sudo
Попробуй выполнить
sudo aptitude update
sudo aptitude install infinity-theme
PS: В синаптике можно воспользоваться поиском по названию пакета.