Is the file really an executable? Or is it a script which is calling other executables, one of which may not have the executable bit set? Or maybe it is a project with some default tool set which has lost its executable bit?
If none of that works, ISTR there were problems getting that archive to decompress without corruption (in the "Please stop copying Starfighter" thread). You may want to contact the author and try to get a new copy of that file in case it is corrupt.
--
moto