If it's the same as any other ISP, then they'll very likely be running any scripts within the cgi-bin directory using suEXEC. This means that the script needs to have 755 permissions set. Any other combination will cause it to fail.
See this link for more details of my ISP.....