After upgrading to Ubuntu 13.04, I was facing this problem. I was not able to execute any script file just by double clicking on it, even though it has execute permission. Then I figured out, how to fix this problem.

I opened the file explorer Files. Pressed Alt+F10 and selected Preferences. It showed something like this.



In the Behavior tab, I selected Ask each time and closed it. By default, it was in View executable text files when they are opened. Now whenever I double click on a shell script, it will ask me what to do. If you want to straight away execute the script, select the first option Run executable text files when they are opened.