You are Exporting ( Outputting) your HD Sequence as an SD Movie (ie 16: 9 to 4:3)
Check the AME H264 Export Settings and see if there is a You Tube Preset.
Tip : When using the Export Application (AME) take a look at the Output Tab. to check that things look right.
Another issue besides the aspect ratio is that you're ouputting to a interlaced format. Which for web viewing isn't a good idea. If web is the intended viewing place you want to use progressive field order settings. However please note this isn't what is causing the problem you've already noticed but it will cause your footage to look "jagged" among other issues.
I'd also recommend exporting to something other than Microsoft AVI for you-tube videos. I'd recommend using h.264 because this way you can just use Premiere's built in you-tube settings. Since you're not used to doing this yet.
The other idea I'd recommend is outputting your video at the highest resolution possible. In the screen shot you posted you're lowering the resolution. For you-tube content I generally always like using 1280x720 for my resolution settings. For shorter clips I sometimes use 1080, but since you're using HDV sequence settings I'd recommend just exporting to 1280x720 since it's not going to be 1920x1080 anyways.
I export my 1920 x 1080 HD projects as Quicktime h.264 movies at the highest quality out of Premiere. Then I just upload it to You Tube and it recognizes that its an HD file. I get great results this way. Here is a recent example. Please set the resolution to 1080p and make it full screen when you view it on You Tube. I assume you know where those controls are on the lower right of the frame.
I don't have CS5.5 - all I have is CS6. However, in CS6 there is a preset for YouTube in the H.264 settings. Works for me. I usually use Vimeo, but I have this example on YouTube.
One interesting note. The Vimeo setting is for 5Mbps while the YouTube is for 8Mbps.