Eversince I upgraded my kernel to 2.6.9, I was unable to start wine properly. Up until kernel 2.6.8 everything was going great. So this must be a kernel thingie, right?
After Googling 'round a bit, I found the solution.
It seems that adding the following line to your /etc/sysctl.conf did the trick:

vm.legacy_va_layout = 1

Now you want to run 

sysctl -p

to load the parameter.
Now all your beloved games should run perfectly on a 2.6.9 Linux kernel.