fisk0: UPDATE: I can confirm it runs perfectly in Wine 1.2 (pretty old by this point, I think the most recent is 1.5, and I don't think they would have worse support for it by now) in Ubuntu 10.04, with one notice - the shortcuts created by the GOG installer don't work. Not sure if it's the GOGwrapper not working fully, or if it's the complex style of link (starting gogwrapper.exe with a lot of command line options and stuff) that causes it to fail to start. But if you go to the game's install directory (.wine/drive_c/Program/GOG.com/Krush Kill N Destroy Xtreme) and start kkndgame.exe from there, it ran flawlessly for me, at least for the about 5 minutes I tried it. I just watched a couple of FMV sequences and started a KAOS Mode match against the CPU, constructed a couple of buildings and closed the game. No problems whatsoever doing that.
Oddly this reply didn't flag up on my account. I only found this by browsing this forum and noticing an extra reply.
Thanks for taking the time to test this, I can brush the cobwebs off my wallet now.