The Easy Setup you chose was correct. However, changing the Easy Setup does not change the sequence already in your browser. To do that you need to create a new sequence or tell the current one to conform to the clip's settings, as you did.
Before exporting, make sure everything is rendered out (Option-R). Then select these settings in Quicktime Conversion if you didn't already:
Format: Quicktime Movie
Compression Type: H.264
Frame Rate: Current
Data Rate: 5000
Key Frames: Every 25 frames
Size: 1920x1080 (I sometimes downscale to 1280x720)
Deinterlace: Yes
Optimized for: Download
Prepare for Internet Streaming: Fast Start
Audio: AAC Compression
To be honest, your Youtube video didn't look that bad. I didn't notice the "fuzziness" that you saw and the only thing that I noticed was that it wasn't very smooth. This could have been because of the deinterlacing or a jerky tripod/filming situation.