It's unclear whether you describe clicking a Start Menu shortcut, or the
.exe file directly.
If you cannot run any
.exe files from Windows Explorer:
The new user accounts (and the "Default" account, which Windows uses as the template) might have corrupted file associations, pointing all
.exe files to another program (often – malware that has been incorrectly removed).
Log out of all affected accounts, log in as an administrator, then delete the file
Local Settings\Application Data\Microsoft\Windows\Usrclass.dat from every affected profile.
C:\Documents and Settings\Default User\Local Settings\Application Data\Microsoft\Windows\Usrclass.dat.
Usrclass.dat holds per-user file associations, and is reasonably safe to delete (on most systems, it'll only have less than a dozen associations which can be easily fixed – the rest are stored system-wide).
If you get "File in use", run
regedit, expand the
HKEY_USERS key, and unload all subkeys named
<sid>_classes (using File → Unload Hive).