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
.