Drupal 6 : Evil taxonomy hierarchy bug, leaves your hierarchy not working
The vocabulary edit form hardcodes the value of the 'hierarchy' flag to '0', therefore resetting it when the form is submitted and the vocabulary saved. (from drupal.org)
You also need to resave your vocabularies.
You will probably have discovered this bug while working met facetted search.
What should you do?
Change in taxonomy.admin.inc line 172 from
'#value' => '0',
'#value' => $edit['hierarchy'],