I'm using Ubuntu 13.04 (though I've had this same problem on 12.10) and am running Samba with some shares set up so I can run some Windows tools (.exes) directly from the shares. Every Windows computer I've tried to run the programs on from the share give a permission error.
The shares are read-only, have guest access and are created simply through the "Share" tab of Nautilus properties. If I check the box "Allow others to create and delete files in this folder", they are able to execute fine, but this isn't ideal. There's no issue reading any other type of file or even copying the .exes over to a temporary location on the Windows machine and running it. Changing the executable bit makes no difference (desperate!).