Para executar um arquivo de texto como executável do nautilus, duas coisas precisam ser definidas. Parece que você já fez o primeiro.
O segundo é que o arquivo precisa ser marcado como executável.
Para fazer isso do nautilus clique com o botão direito do mouse no arquivo e selecione "propriedades"
depois, na aba "Permissões" selecione "Permitir a execução do arquivo como programa".
Ou na linha de comando
chmod +x file
substituindo o arquivo pelo nome do arquivo.