Comment 23 for bug 14335

I don't believe this problem is a Nautilus bug. The exec permissions are the same to Nautilus as they are to other file managers such as KDE's Dolphin. Moreover, this very same problem also affects any shell.

So, to put it in other words, the problem behind this is the poor choice for the default traditional UNIX permissions that are attributed to FAT (and maybe other) file systems which don't support traditional UNIX permissions. From there, File managers and the like are dragged down by this bug.