Much depends on the source video and which project settings you're using in Premiere Elements.
Did these AVIs come from a miniDV camcorder, captured over FireWire?
If not, they may be using a codec that's not a good fit (video from a still camera, for instance) and you may need to convert it first.
Additionally, YouTube does a lot of damage when it re-encodes whatever you put up there.
The FAQs to the right of this forum offer a workaround to avoid much of this damage.
I'm not the person to comment on anything YouTube, but maybe there will be something of help in this FAQ Entry?
Dang it! He did it again, and no phone call this time... Oh well, he knows far more about YouTube that I ever will.