I'm not really familiar with uploading on youtube, though, from some research for a project of my own, I know that there could be a number of things affect your video quality. For one, if you try and make a standard, non-HD video into an HD video, the effect which you are describing will happen. The video will be stretched to fit the screen and there will be a significant drop in quality. So, if you want what you are uploading on Youtube to be widescreen, make sure that the files you are uploading were recorded to fit a 16:9 (HD) format instead of a 4:3(SD) format.
A second thing that may be affecting your video quality (and this one may not apply to you at all) is the codec you are using to compress your files. The codec you use will ultimately determine how good the quality of your video is. Xvid and Divx are to pretty good codec's that are also free. You could also try Laigrath lossless codec, which is what I've been using.
Finally, make sure the files you are uploading to Youtube is an MPEG4 format with MP3 audio. While Youtube will accept AVI files, MPEG4 works better.
Hope that helped.