I have the same problem.
For example, the binary for Neverwinter Nights is in /home/user/NWN/
And to run it, I would go to that directory and at the bash prompt type ./nwn
I wanted to make an icon for it on my root window, and so made a shortcut pointing to /home/user/NWN/nwn and it didn't work. Tried telling to run in a terminal. Didn't work. Tried changing it to ./nwn and it still didn't work.
I've yet been unable to figure it out.