I'm pretty sure I've run NB in a very recent ubuntu in a VM without troubles. Offhand, it sounds like a permissions issue - sometimes how things are setup with mapping ownership between OSs can lead to oddities. If you want to run it the way Ubuntu expects you to, you're right, I think you need to mark it as 'executable', but your inability to change that suggests it's permission based.
Try 'chmod oug+rw thenewsbininstaller.exe' and see if that helps. You may need to sudo, not sure...Ubuntu tends to impose it's own way of managing permissions(one reason I don't care for it, as a long time linux user
), so perhaps it's one of the permission things you can get with the GUI approach of right click/properties or similar.
You don't mention releases of Newsbin, I assume you're using a recent one(which has the 62/32 bit release from the single installer)...