Recently the hardware abstaction layer (HAL) was changed so that FAT volumes are mounted with the "showexec" mount option. This is not specific to AppImages, it effectively prevents any executable from being executed on FAT partitions (even shell scripts). You can find out if you are affected by this by typing "mount" - if you see "showexec" in the output, then that is the likely reason.
There is a hack you can use to revert the behavior back to normal:
http://ubuntuforums.org/showthread.php?t=1665289