Drupal upgrade problem

So, I am in the process of upgrading to Drupal 6 (took long enough to get OKs from the higher ups). I have been researching how to do a "smooth" upgrade. I have gotten our custom theme nearly updated, and other kinks worked out. We have over 6000 pages in our installation and about 1000+ links in our menus/sub-menus/role-based-menus. Now, making new menus for our 8 other languages is not very practical. I can switch languages on the pages just fine, but my menus have not updated properly in the upgrade process.