I get similiar results. I am told You Tube is recompressing the footage which makes it look like that. You may want to try www.sharkle.com and see if that helps. Comparing the 2 sites, I have found better results using Sharkle but its still not like I want it to look yet.
Yeah, basically you can imagine them encoding your already encoded video to their format. I guess the best advice is the start from as best a source file as you can so when you export your video for the first time, make sure it's as high quality as you can allow.