First of all, gaming under Wine on Linux works best if you use a nVidia card, GeForce 6000 series or better. ATI may or may not work as ATI's Linux driver has limited OpenGL functionality. If you have some other card such as Intel integrated graphics, I wouldn't count on it to work. Also note, you need an x86 based computer (normal PC / Intel Mac) if you use a nVidia graphics card as the nVidia driver only supports this platform.
I am running Debian 6.0 testing and use the latest wine (1.2-rc7) compiled from source. It should also work with the latest stable version of Debian 5.0. If you try Debian, after installing Debian, follow these steps.
Install the lastest Linux driver for your graphics card (recommended) or install the Debian package.
Create a directory inside your normal (non-root) user's home directory called "src"
Download the latest wine source (.tar.bz2 file) from
www.winehq.org into the "src" directory.
Open a terminal.
Enter "su" to switch to root.
Enter "apt-get update" to allow the package manager to know what packages are currently available.
Enter "apt-get build-dep wine" to install build dependencies for wine.
Enter "exit" to go back to the normal user.
Enter "cd ~/src" to change to the "src" directory.
Enter "tar -xjf ./wine-1.2-rc7.tar.bz2" or change this to use the proper file name to extract the source archive.
Enter "cd wine-1.2-rc7" or change this to use the proper file name to change to the wine source directory.
Enter "./configure" to configure the source for building. This may show a few features being unavailable but this should be ok.
Enter "make" to build wine from the source.
Enter "su" to become root again.
Enter "make install" to install wine.
That's it. Wine should now be installed.
These directions should also work for Ubuntu and many Ubuntu/Debian based distributions. You may have to use "sudo" instead of "su" to root. However, I am not sure about that as I only use Debian. This general procedure also works for other distributions. You just have to replace the "apt-get" commands with those appropriate for your distribution. Also, if the frame rate is choppy, try using the lowest graphics settings in-game. I hear that using anything other than bilinear filtering will kill your frame rate, so use bilinear. I hope this helps.