I had this issue, and Worm helped me out. (His solution above didn't work for my case, but we tried this)

He had me reinstall a seperate steam game. And it caused Toribash to work. Not sure how it does that, but it worked.