Currently I'm working on a 6-language website and all content obviously needs to be translated, including menus. For this, I have enabled i18n_menu and i18n_select (as I had a little experience on the latter regarding this issue), translated the originally French node to English, and both menu items show up when I go to English translation of the node. Any ideas?
I suppose you added the french menu item before you added additional languages to your Drupal. Then it is very likely that it was saved using LANGUAGE_NEUTRAL as language and therefore will appear within all languages.
To fix this, go to the menu's item list on admin/structure and manually edit the menu item. You should find a drop down for the language within the edit form. Make sure to choose the appropriate language here and save the item.