Кажется, что правильное имя пакета: `nautilus-open-terminal-here
Итак:
sudo apt-get install nautilus-open-terminal-here
В будущем вы могли бы использовать старый добрый Synaptic, чтобы найти пакеты вам нужны:
sudo apt-get install synaptic
С синаптической системой легко найти и управлять пакетами, когда они находятся в затруднительном положении. Более подробно этот программный центр и проще обрабатывать, чем командную строку.