Which filesystem are you using for the disk where Steam is installed? If you're not using ext2 or ext3, consider giving them a try.
The problem is essentially a bug in Steam. It is a race condition around the disk caching behavior. As I understand it, when you run a game, this happens:
1) Steam unpacks a few files(usually 10-100 mb) from the gcf files to disk
2) It starts a timer, waits for the new game to connect
3) It closes the preparing to run dialog and starts the game
4) The game connects to steam and continues loading the rest of the files using IPC.
5) If the timer times out it assumes the game failed to start and closes the connection
Now when Steam unpacks the files, some data has to be written to the disk. Depending on the size, hardware and other factors, this can take a few secounds. On Windows, this happens during step 1, or at least before the timer starts. On Linux, the files are cached longer in RAM for better disk performance, and are written back at some later point. If you have bad luck, this happens during 3 and 4. The writeback delays the game start a few secounds, so the timer may time out. Then the game finds out that Steam doesn't listen to it, complains and terminates.
We have a workaround for this: On file systems that support it(ext2, ext3 at least) we set the synchronous +S flag using chattr when installing Steam. This makes linux write the files to disk on step 1, so the timeout is avoided. This has virtually eliminated the problem for users with those filesystems, but XFS and reiserfs users, or users which do not install Steam using CrossOver but copy it from somewhere else still suffer from this problem.
This problem can be reproduced on Windows as well. Users which have some system tuners which change the caching parameters often report the same issue. I think it is partially documented in the Steam FAQ as well.