Brooklyn,
My Quicktime Pro key expired, so unfortunately I can't go and look to see what I did, but I had the same issue as you. I believe that the issue revolves around the "Save as" function. If I remember correctly, and again, this is going back a couple of years to when I used to use QTP, I believe once you rotate the video portion of the video, you have to actually do an export to a new file, instead of saving it.
When you just do "save as", I believe all that is done is the exif data for the video is changed so that any Quicktime programs will display the video with the proper orientation, but aftermarket programs, like VLC, don't read all of the data, and therefore play the video as it was originally intended.
I know there is a thread in the Apple Quicktime support forums on Apple's website (probably thousands), as that is where I found the correct way to export the videos so that they play properly. If I have time later, I'll see if I can scour the interwebz for the specific answer, but in the mean time, check out Apple's site and see if they have the walkthrough.