Do you have a real ATI driver installed or are you only using some basic 2d thing that comes with X? I'm only familiar with NVIDIA stuff and I know that the game runs alright for me with NVIDIA's driver and current development versions of wine (1.1.31).
