taxonomy tree block

I had the same problem. I found some code (#133090-11: Fails validation due to incorrectly nested lists.) and fixed an error. You can make into a function or paste into a block (with some minor modifications) to get a taxonomy tree

function theme_taxonomy_link_tree($vid=1){
$last_depth = -1;

$rss_depth = 'all';
$cat_depth = 'all';

$show_count = FALSE;
$show_rss = TRUE;

$output = $description ? '<div class="description">'. check_plain($description) .'</div>' : '';

$output .= '<div class="tree">';
// taxonomy_get_tree() honors access controls
 $tree = taxonomy_get_tree($vid);
 foreach ($tree as $key => $term) {
    // Adjust the depth of the <ul> based on the change
    // in $term->depth since the $last_depth.
    if ($term->depth > $last_depth) {
      for ($i = 0; $i < ($term->depth - $last_depth); $i++) {
        $output .= '<ul>';
      }
    }
    elseif ($term->depth < $last_depth) {
      for ($i = 0; $i > ($term->depth - $last_depth); $i--) {
        $output .= '</ul>';
      }
    }
// Display the $term.
    $output .= '<li>';
    $term->count = taxonomy_term_count_nodes($term->tid);
    if ($term->count) {
      if ($cat_depth < 0) {
        $output .= l($term->name, taxonomy_term_path($term), array('title' => $term->description));
      }
      else {
        $output .= l($term->name, "taxonomy/term/$term->tid/$cat_depth", array('title' => $term->description));
      }
    }
    else {
      $output .= check_plain($term->name);
    }
    if ($show_count) { 
      $output .= " ($term->count)";
    }
    if ($show_rss) {
      $output .= ' '. theme('site_map_feed_icon', url("taxonomy/term/$term->tid/$rss_depth/feed"));
      $output .= (module_exists('commentrss') ? ' '. theme('site_map_feed_icon', url("crss/term/$term->tid"), 'comment') : '');
    }

    if(is_null($tree[$key+1]->depth) || $tree[$key+1]->depth == $term->depth) {
        $output .= "</li>\n";
    }
    // Reset $last_depth in preparation for the next $term.
    $last_depth = $term->depth;
  }

  // Bring the depth back to where it began, -1.
  if ($last_depth > -1) {
    for ($i = 0; $i < ($last_depth + 1); $i++) {
      $output .= '</ul>';
      if(!$tree[$key+1]->depth && ($i < $last_depth) ) {
        $output .= "</li>\n";
      }
    }
  }
  $output .= "</div>\n";
  $output = theme('box', 'Departments', $output);

  return $output;

}