When going to drupal 6 I needed also to upgrade our theme.
I had everything quiet fast, just the menu-tree was a big pain.

The code for the drupal 5 theme was:
print theme('menu_tree',variable_get('menu_primary_menu',0));

And now for drupal 6 it is:
print menu_tree($menu_name = 'primary-links');