Hmm... what do you get when you do md5sum NVIDIA-Linux-x86-1.0-4363.run?
I get this:
Make sure your MD5 sum matches that; if it doesn't, you got a corrupted download (or something similar).
Or, I think you can pass a --check option to the installer when you run it (I'm assuming the "can't execute" message isn't from the script, but rather from some binary it runs). You could also pass --extract-only, cd into the new directory, and try to run ./nvidia-installer from there.