May I ask what version of Linux you are running on and what graphics card you've got in there?
My colleague had a very different problem (game wouldn't even start for him), so I think I'm rather going to pull the Linux version for now until I get time to setup a test machine where I can troubleshoot.