Você precisa ter a permissão correta (leia + executar) no diretório que contém o executável também.
Se você tiver um script chamado script.sh in /home/foo/ e ele tiver a permissão octal de 775.
Agora, se você deseja executar o script como um usuário diferente, por exemplo, bar , então bar precisa ter permissão de leitura e execução nos diretórios / , /home e /home/foo senão bar receberá uma mensagem de permissão negada, independentemente da permissão de /home/foo/script.sh .