Okay, I've talked to Valve, and there doesn't seem to be anything that would have caused that from their end. Our staff on windows computers have also tried it out, and it worked fine. So it doesn't seem there is a wider problem here, though we'll keep an eye out.
My general suggestion when things mysteriously stop working all of a sudden like this, once anything service-related has been ruled out, is for you to make sure that:
1. It's a good idea to run a scan for both viruses and/or spyware. With AI War, we had several player that had spyware messing things up, but I don't know if that's the case here or not. Running ad-aware, spybot s&d, or avg free or similar are all free and great for that.
2. It's also a good idea to do a scandisk on your computer (instructions for that vary by computer OS, but it's pretty simple). It could be the early signs of hard disk failure if files are spontaneously combusting and yet still passing hash checks of the sort that Steam would do to verify your local file cache. We had at least one player with AI War where this happened.
If either of the above is true, doing a reinstall of Tidalis, as you were planning, would solve the immediate issue. But, you might have it recur if you don't either remove the spyware or run a scandisk, whichever problem it might be. Scandisk can actually flag bad disk sectors so that they don't get used again, which is great for protecting against a recurrence in Tidalis or otherwise.
Of course, it could have been just a hiccup with Steam, and you reinstall and have no problems from then on. But, when a hiccup occurs, it's good to check the other things out if you haven't lately, just to be sure your computer isn't in for a worse problem unrelated to games in the near future.
Hope that helps!