Seus scripts provavelmente têm terminações de linha CR-LF no estilo DOS e não terminações de linha LF no estilo Unix. O ^ M visto na mensagem de erro no primeiro caso é uma indicação de que o caractere 0D foi interpretado como parte do nome do interpretador de script e não como parte da terminação da linha (como se poderia esperar que seja). Como não há nenhum arquivo executável em seu sistema com um caminho que inclua o caractere 0D (^ M), o sistema não pode chamar o intérprete. Quando você chama seu intérprete manualmente, ele consegue lidar com os dois tipos de final de linha presentes no script.
Se você converter os scripts para usar finais de linha LF no estilo Unix, deverá ver o shebang funcionando. Leia para uma ilustração.
Na sessão abaixo, todos e fromdos são um utilitário (disponível no Ubuntu como o pacote tofrodos ) para converter as convenções de fim de linha de CR-LF para LF. Qualquer utilitário equivalente (consulte esta questão unix.SE ) faria com a finalidade de demonstração.
A seguinte transcrição da sessão (executada com os mesmos arquivos de script) deve esclarecer a situação:
$ fromdos hello.sh
$ ./hello.sh
Hello
$ todos hello.sh
$ ./hello.sh
bash: ./hello.sh: /bin/sh^M: bad interpreter: No such file or directory
$
$ fromdos hello.py
$ ./hello.py
Hello
$ todos hello.py
$ ./hello.py
: No such file or directory
$
parece que é o kernel que lê a linha shebang, e aparentemente o kernel Linux (pelo menos a partir da versão no meu sistema Kubuntu Saucy) não reconhece o CR como parte da convenção de terminação de linha CR-LF.
Se o shebang do seu script não estiver funcionando (ou seja, chamar manualmente o interpretador no script funciona, mas você não pode executar o script usando o nome dele mesmo que tenha feito chmod +x nele) então esta é uma razão possível.
NOTA: Obrigado aos outros que comentaram também. Eu também ficaria feliz em saber se há melhores respostas!