Below is how I resolved this before, for a multilingual D7 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 (e.g) 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 all 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 ...