Indeed, as you suspected yourself, this user case is not anymore supported. Since a few versions, .desktop files in the file manager do not anymore present themselves as launchers, but as plain text files that open in a text editor. In fact, the whole concept of just executing any file by double-clicking has been deprecated in the Gnome Desktop (with nautilus). For media, some standard installed applications can be autostarted on insertion, (e.g. you media player on inserting an audio CD), but you cannot automatically run anything from an inserted medium.
This is inspired by safety concerns. It eliminates that users inadvertently run software, which could do damage at that moment, and even could be malicious. The idea is that software should be run in a standard way (through icons or through typing the name of an executable properly installed in the search PATH, although it remains possible to run an executable anywhere by typing the full path (including ./... for an executable in the current directory). The latter, however, will much less likely be done by accident.
Obviously, in your use case, that renders deployment of a tool from an inserted drive (somewhat) less user friendly.
The most user friendly approach probably would be to package your software as a .deb file. On double clicking it, the software center will start to prompt for installation. This also would cause your tool to be integrated in the APT system, so it can easily be removed.
You obviously can also work with your installation script, but you will need to provide instructions in a few steps on how to launch it.
