Try right clicking 'Skyrim' in Steam library, go to properties, local files, 'verify integrity of game cache', doing this has solved game launch and other problems for me in the past. As you've already reinstalled Skyrim it probably won't help but worth a try I suppose.
Unfortunately I have done this several times to no avail.
