Все понятно?
В сущности, уже не особо. До этого было яснее. На что именно ругается терминал теперь, когда указываете полный путь?
Касательно Nautilus:
1. Опцию нужно активировать в настройках. Из Gnome это делается так: правой клавишей мышки по следу окна на панели задач вверху экрана -> Параметры -> Вид -> Исполняемые текстовые файлы = [всегда спрашивать]. В Unity та же петрушка, разве что пункт "Параметры" искать следует в меню, выдаваемом по клике ПКМ на логотипе файлового менеджера в панели Unity.
2. Найти сам файл в Nautilus, ПКМ на нем, далее как в Caja - "Свойства" -> "Разрешения". Поставить галочку напротив "Разрешить выполнение файла как программы".
3. Двойной клик ЛКМ на файле - выбираем "Запустить в терминале".
-----
Альтернатива: в Nautilus находим наш Uninstall.sh, делаем клик ПКМ в любом свободном месте в папке, где он лежит. В появившемся меню выбираем "Открыть в терминале", и вводим исходное:
sudo sh Uninstall.sh
/на сей раз без указания ПУТИ, - путь мы уже задали, открыв терминал В ЭТОЙ САМОЙ ПАПКЕ/