O seu computador é x64? Por alguma razão, alguns jogos Steam precisam da biblioteca x86 ... Isso também aconteceu comigo, e o Steam Support me disse para fazer o seguinte:
Open up Terminal
Type the following command:
sudo apt-get install ia32-libs
Você pode precisar colocar sua senha de login por causa do comando sudo
...
Depois de terminar, deve funcionar com qualquer jogo. Se isso não acontecer, talvez seja necessário ativar o Dev. Filial do jogo. Então, para fazer isso:
Right click the game you want to play, and chose properties.
Click in the Betas tab, and select Development Branch from the dropdown and then close the window.
Try to open your game.
Se isso não ajudar, entre em contato com o Suporte Steam. O jogo no Linux é em algum ponto "novo" e ainda tem seus "problemas", então eles devem ajudá-lo.