The Steam Cloud was disabled for a bit while they fixed some bugs.....assuming you didnt overwrite the clusters that the game save was written on...you may be able to recover it.
First thing to note is your game saves are located in My Documents>My Games>FalloutNV>Saves
The easiest and quickest way to check to see if you can recover them is to use the shadow volume built into Windows Vista/7. Even if you reinstall the OS you can get in here and recover files.
Download http://www.shadowexplorer.com/ and navigate to the save games. Then simply copy them over to the newly installed OS in their correct location.