Do you use any subtitles? What happens if you disable them?
You can also try to use "Computer/Data" category in the "Video Output Setup" dialog. Select "YouTube" preset. Click "Encoder Options...". Set "Average bitrate" to 1024, "Maximum bitrate" to 2048. Click OK. Find your movie in the destination folder and upload it manually if it's OK.