There are two three known workarounds for this (see Precog DragonBorn's answer for general Steam issues; these were particular to Skyrim).
The one most frequently found online is to verify your game files:
- right click Skyrim in your library
- click properties
- go to the local files tab
- click "verify integrity of game cache"
- wait a while
- as JClasspill points out, make sure all patches have completed before giving up
A number of people seem to have had this work.
This however, did not work on my system (Windows 7, x64, GeForce GTS 450).
What did work for me was switching Steam to offline mode:
- click the Steam menu
- click "go offline"
Note that this worked even after completely re-installing Steam and Skyrim didn't. I suspect, but cannot be sure, this has something to do with Steam Cloud syncing because after attempting and failing to launch Skyrim I couldn't close Steam due to it.
Sean C reports that deleting ClientRegistry.blob can also fix this issue.