How to configure a different main menu for each language on a multilingual site?
Make sure the i18n Menu Translation sub-module is enabled (it is one of the Internationalization sub-modules).

Edit the menu to be translated, by navigating to admin/structure/menu/manage/main-menu/edit (for the "main menu"). From there it should be possible to select the translation mode you want, e.g. Translate and Localize.

After doing so, when editing a menu link, there should be a new link Translate to actually translate the menu entry. Refer to the Multilingual Guide for (way) more details.

Miltilingual sites are really fun in D7 (way better then it was in D6, and D8 promises to become more easy to configure). Typical variations (with similar solutions) of this "menu" topic are:


translations of blocks, which requires the Block Languages (i18n_block) submodule to be enabled.
translations of taxonomies, which requires the Taxonomy Translation (i18n_taxonomy) submodule to be enabled.