I had the same problem.
You will need to use Apples iMovie Editor or Quicktime. on an Apple Quicktimepro is included free.
You can purchase Quicktime Pro for windows - You will get the same lossless experiences for rotating, cutting and re saving to a new lossless HD file.
Using iMovies - It will automatically republish your video in a lossless format, with transitions,cuts,pastes,audio,etc. In the correct orientation without manual rotation.
For Windows or other OS's there is no FREE method to do it and its best to use the Quicktime library at all time.
Using windows.. you will have to re encode it --- I searched and searched. only Quicktime will play it in the correct orientation.. but you cannot tell it to fix the original file. Seems a bit odd.. but that was Steve Jobs philosofy.. It always works like you want on a MAC ;)