When you export a movie you should see a compression settings box in the lower left of the Movie Export Settings Screen. The box has a button for "Compression Settings" shows your compression type and the Frame Size. You want to make sure the frame size matches your project. If it is not navigate to Edit> Preferences then go to the Export Tab...For each export setting make sure "Use Project Frame Rate" is checked.
This should solve your issue, if not let me know and post the export settings you are using.