Holy cow, I too had this problem, but I think I have a fix! Please let me know if this works for you.
I did a quick screen recording using QuickTime 10.2 (iMac 21.5 2.7 GHz Core i5, 16 GB RAM) and saved that movie. Then I tried the Export for Web... and it worked! So now I was suspicious of the movie that I'd been trying to export previously, something that came from iMovie.
When I did Get Info on the screen recording (which led to a successful Export for Web...) I noticed the Codes were "H.264, AAC." When I did Get Info on the exported-from-iMovie movie, the Codecs were "H.264, Linear PCM." I don't know much about these formats but I thought that maybe if I could get my "bad" movie to have the same Codecs as the "good" movie maybe it would work.
Bad movie on the left. Good movie on the right.
To change the Codecs I used QuickTime 7 Pro but it looks as if you could use the non-Pro version too. I got the bad movie open, then File/Export... and chose "Movie to QuickTime Movie." I clicked the Options button and made it look like this:
This makes it look as if the issue was with the SOUND part of my "bad" movie, which maybe it was. I did do a few things in there-- including a voiceover, which might have been the problem come to think of it.
Anyway... once I'd opened the "bad" movie and done the File/Export... "Movie to QuickTime Movie" thing, I quit QuickTime Player 7 Pro, and then I opened the new movie using QuickTime Player 10.2, and then I went to File/Export To/ Web... AND IT WORKED.
I think I will write this up on my blog. And I hope what worked for me works for you.