YouTube transcodes video you upload. The video codec you're using isn't compatible with YouTube, it seems. Are you uploading in MPEG2 format, or what? Either way, you should compress videos as little as possible before you upload them, because YouTube needs to transcode them further, reducing quality (and sometimes introducing glitches, it seems.)
Alternatively, you could upload video encoded in H.264 (recommended) or even VC-1. There are easy to use tools out there for transcoding video, such as
HandBrake. Just keep in mind that you should limit the amount of times you transcode video before you upload, as each step eats away at quality. Ideally, you'd upload the originals to YouTube, but that can be problematic. What I do is upload high-bitrate H.264 video and it seems to work out okay, although I am by no means an expert when it comes to video encoding and YouTube. ):
YouTube has a help page that details which formats are recommended for uploading that you may want to look into as well.