Similar problem here after upgrading (!?!?) from SL to Mavericks.
Since Mavericks the MP4 files from my Samsung SD Camcorder had the following probles....
Quick View played video but no audio.
Quicktime displayed th following message...
"The document “HDV_0002.MP4” could not be opened. This media may be damaged."
VLC however still plays them with no problem.
I have found a work around but it makes little sense. It seems to prove that it is not a codec problem but the way Mavericks and or the latest Quicktime is reading the files.
On a hunch I used Miro Video Converter (free) to convert the problematic MP4s to the same format and 'hey presto' they work both in Quick view and quicktime!!!
Same container, same video and audio codecs. Nothing i can see thats different in the finder get info window or the 'media information window ' in VLC.
Go Figure!
Not a perfect solutioin as the process still takes some time but Miro will batch convert.
Hope this helps some of you.