Definir a permissão "executado como programa" não é suficiente, pois há uma preferência global do Nautilus que altera o comportamento quando você clica em um arquivo de texto executável.
Abra as Preferências do Nautilus (Editar - > Preferências) e selecione a guia Comportamento:
Selecioneaopção"Perguntar a cada vez" para obter o pop-up a seguir ao clicar em seus arquivos .sh :
