It runs on my Wine 1.5 Ubuntu 12.04 64 BIt Linux. But even with virtual desktop set to native resolution, the game runs in window mode and is rather slow. Any chance to get it in fullscreen?

Check this script I used for Fallout that present a similar issue (scroll down a little):
http://www.gog.com/forum/fallout_series/linux_playability_fallout_series