If using the pre-settings remember you have two options SD and HD. When selecting the HD option your export won't appear to be letter-boxed (black bars).
Letterbox means that a 16:9 widescreen video, played on a 4:3 display, has the black bars top and bottom. From my understanding 1920x1080 will give you bigger bars than if 720. If uploading to youtube or FB the black bars are pronounced even though the bars to appear on the file when viewing for example on your computer.
I can't really determine if the black bars you're getting are abnormal without a screenshot. But here is some detail info from Adobe on exporting. http://helpx.adobe.com/media-encoder/using/export-settings-reference.html#video_exports_settings