"Failed to initialize the GameStartup Interface" when trying to run Crysis 2 demo
This kind of error can sometimes be solved when you verify the game fragmentation, through the game options.
Game fragmentation usually happens when you download too many games at once through Steam, or when a game is being downloaded by too many people at once.
It can also be caused by running a process which does a lot of disk access.
I had the same error. This is how I fixed it:
Copy all .dll files from the "bin32" directory and paste them in the main directory.