Since the menu system checks what languages are present when creating the language tabs, if you add a new language, the new language tab isn't available until you rebuild the menu structure. This is something that will be fixed in Drupal 7, but for Drupal 6, we're out of luck.

We'll have to find a way around this.