While I had the same problem, I couldn't find any solution on the web that worked. I tried something and it worked for me.
Here is what I did :
BTW, I use Windows 7 x64. The file path may be different on XP or Vista.
1. Go to your game folder (C:\Users\[Your User Name]\Documents\My Games\Sid Meier's Civilization 5).
2. Change the folder named "Sid Meier's Civilization 5" to anything else (I personally added the date after to know what I'm referring to, so it was "Sid Meier's Civilization 5 - 2011-03-14").
3. Go to the steam game folder (C:\Program Files (x86)\Steam\steamapps\common\sid meier's civilization v).
4. Change the folder named "sid meier's civilization v" to anything else (I personally added the date after to know what I'm referring to, so it was "sid meier's civilization v - 2011-03-14").
5. Now, restart steam (you may need to reboot your computer to make sure everything is fine).
6. Open Steam, from the "Library" menu, right click on your Civ 5 game, then left click on "Properties".
7. Select "Local Files" tablet, then click on "Verify integrity of game cache". Follow instruction on screen.
8. Steam will think that Civ has disappeared, and will now redownload it from the internet and install a fresh copy. Beware, if your internet is not unlimited, it may be expensive has you will have to download a fresh new 5 GB copy of the game, just like the first time. If your internet is slow, you may want to start this process before to go to work or to bed. It took me 3 hours to download everything, so it's long.
NB : I tried before to verify integrity of the game through Steam, and it didn't work, I also reinstalled it from the web, and it didn't work. I only worked after I change the names of those 2 folders. I suspect a file got corrupted somewhere.
BTW, if you want to play your good old savegames, after everything is done, all you have to do is copy your savegames folder from the old folder into the new one. Same for mods and other stuff.
It worked fine to me. Tell me if it works with you!
