Last Monday I released a patch for AutomaticMenu to make it Drupal 6 compatible. While I was at it, I included i18n support, with the possibility to select a different parent menu item per language per content type. I use it at a customers site and no problems reported so far. You can find more information about the patch and the port in total at http://drupal.org/node/275889