Try the YouTube preset on export.
How long is it?
What format are you exporting?
Like Harm said " use the YouTube preset "
Just click H.264 then YouTube HD
Since you are recording at 1920x1080 raise the level up to 4.1 and increase the size up to fit your video. Make sure the frame rate is the same since it likes to change when raising the levels. Check the audio and make sure it matches your source and then Save this has your YouTube HD 1920x1080 size.
I dont know why Adobe doesnt have a 1080 & a 720 HD preset but at least you can make one.
After that it should be good.