The partition the file(s) resides on, is it the FAT32 by any chance? If so, try moving it to another partition and try chmod again. For setting execution rights, people have reported different results executing chmod +x versus chmod 777.

If nothing works, I´d do a unmount -> filesystem check -> mount sequence.