I've been struggling with a similar issue in the past too. Below is how I resolved this for a multilingual site with menus in multiple languages. In this case for the "main menu", but you can do this for any menu.
Use a single "main menu" that contains all menu items for all languages, so not 1 main menu for only EN menu items and another main menu for only FR menu items.
Configure the multilingual options of the menu via the Menus administration page and follow the "edit menu" link to the menu in question. For the Main menu that would be
For "Translation Mode", use the option "Translate and Localize". So that
menu items with language will allow translations, and menu items without language will be localized.
Add the links for any of your languages to the single menu, but make sure to specify for each of these links for which specific language you want the link to be shown. Or as an alternative, if you have menu items that should be shown for al languages, make sure such link is marked as "Language Neutral".
For any language the very only (single) "Main menu" is shown. However based on the selected language, only those menu items in it will be shown that match the selected language. Not sure if it is the best/most elegant way to make this work, but IMHO it works like a charm ...