Rodar Programa sem Compilador

Galera, depois de algumas semanas, criei um programinha (ou script, chamem como quiser) em python, com interface gráfica usando GTK... ta tudo OK no programa...
Depois de terminado fui testar ele fora do compilador python... Peguei o arquivo principal, configurei como executável e cliquei duas vezes nele. Ai o meu Ubuntu me abriu aquela janelinha: deseja executar, abrir como texto, executar em terminal... etc. Selecionei executar... e NADA! tentei denovo com executar em um terminal e... NADA!

Como faço pra executar esse programa clicando no arquivo dele? Ou não tem jeito??

Obs: só confirmando que no inicio do arquivo tem o #!/usr/ bin/python