This appears to be the cause of what I wrote in this issue: http://drupal.org/node/470174
Looking through the youtube.inc file under providers for video_cck, in the function video_cck_youtube_thumbnail, we see the code:

// if we have a large thumbnail size, then get the larger version available.
  if ($width > 130 || $height > 97) {
    $tn = "http://img.youtube.com/vi/$youtube_id/0.jpg";
  }
  else {
    // youtube offers 3 thumbnails. select one randomly.
    $rand = rand(0, 2) + 1;
    CCD $tn = "http://img.youtube.com/vi/$youtube_id/$rand.jpg";
  }
  return $tn;

The width and height fields are sometimes empty. This causes the random smaller thumbnail to always be selected, which doesn't scale well. The larger thumbnail (0.jpg) does scale well.

It appears that whatever function calls this one is not sending in the width/height setting put forth on the settings page. This is why I am entering as a bug report. A work around for the blurry problem is to make it always select 0.jpg.