premiere pro is an absolute exporting whore. I physically detest it. You have to get all your settings correct right from the start or it will stretch or compress your final video and make it shitty. Really annoys me.
For the record the problem you are talking about isn't letterboxing it's actually known as pillarboxing just so you know! The former is where you have black above and below.
Anyway that's irrelevant, I don't actually know what you can do to sort it out. I made the move to FCP because...it's better and easier.