Thank you all for the wonderful feedback. We're working as quickly as possible to verify each problem, find a fix and get it in.
Yesterday, we made a small patch to the Steam Linux Installer: The issue was with the line endings in the script that runs the game. Our version control system had converted the line endings from LF (as required for Linux) to CRLF (as used on Windows) so the script did not execute correctly. Steam will automatically download this update and the game will run.