Eu instalei o Nautilus-open-terminal, mas ainda não estou recebendo a opção Open terminal.
Você também pode simplesmente executar nautilus -q na linha de comando.
nautilus -q