I had the same problem with my Special Edition disc on my PC. I also bought the game from EB games in Australia.
To play Machinarium I did the following (please excuse the non-technical language
):
1. Insert the disc
2. Go to Windows Explorer and right click and select Open on your disc drive
3. There should be a file there called "Machinarium_PC"
4. Copy and paste that on to your desktop
5. Double click on the icon on the desktop
6. The install ran and it created a proper icon on the desktop that I could click on to open the game
For some reason clicking on the icon in my disc drive didn't work.
Hope this helps!