I am having the same issue. Windows Server 2008 R2 - Terminal Server.
We use RemoteApp and our host terminal server is unable to run any EXE.
I have tried uninstalling the updates, but they fail and cannot be removed. I also tried running in safemode, but nothing works from there either.
I saw someone had success running sfc /scannow, I am trying that. I will let you know if it works for me.
***COME ON MICROSOFT??? REALLY??? REALLY????