What was your source footage? Was it progressive to begin with?
I'm assuming it isn't since you said you tried deinterlacing although I'd just like to make sure before I give a answer. It looks like there is some type of interlacing issue occuring. Anyways though tell me your exact sequence settings, frame rate and source footage attributes and also your exact current export settings you used. Also did it look okay before you uploaded it to youtube?
Then I will do my best to give you a possible answer.
What is the final destination of your footage?
If its Youtube use a YT preset or a HDTV preset.
These presets export automaticly to progressive.