I am running Debian testing and I am not able to run any binary or shell script. I keep getting "No such file or directory" for binaries and "Permission denied" for executable shell scripts. The umask is the default one and I haven't fooled around with the paths. Also, I am aware of this question, but it doesn't work out for me - I compiled my code on this machine and trying to run it on the same machine. Also, all of my shell scripts have the correct shebang.
Edit: I am not running any Armor or SELinux kind of application.