The render presets for YouTube aren't very good. The quality of the output is poor.
For decent-looking HD results, I have been rendering to file in MPEG-4 format with a bitrate set at 12,000. This gives me much better quality (still not as good as other video I see on YouTube though), but the biggest problem is file size. For a 7-minute clip it's over 550 MB.
There's got to be some render settings out there that KDEnlive users are using to upload HD video to YouTube.
Please share! (and please incorporated into the KDElive presets!)

Thanks for these, guys. I will be creating a new video on Wednesday and will try rendering with your profiles to see what happens.