Menu links not being translated
Here is what I understand with the current Drupal 7.32.  The behaviour of the i18n in Drupal heavily depends on the settings, so I mention the way I am fairly familiar with.  If your settings are different, the behaviour can be different.

First, i18n_menu must be enabled, as well as i18n_node (I understand some people prefer Entity translation, whose behaviour must be different, but I don't know about it).

Second, give "URL" with "Path-prefix" the top priority at /admin/config/regional/language/configure.  Also, personally I much prefer to explicitly set the path prefix for the default language (usually English, "en") at /admin/config/regional/language/edit/en.  In default it is Null and that is I found quite confusing due to its inherently asymetric nature.  Having said that, it is up to each developer, obviously!

Third, "Translation mode" at /admin/structure/menu/manage/main-menu/edit is the key.  In default, it is "No multilingual options for menu items".  Obviously that is no good for translatable menus.  Choose either of the following two options, that is, (1) "Translate and Localize." and (2) "Fixed Language."

I think the second option (2) suits the most sites, unless the menu stractures for all the supported languages in the website are identical.  If you choose (2), simply create another menu, say, "Main French Menu", tick the "Fixed Language" as French, and place it in the area you like in the block configuration /admin/structure/block

If you choose the first one (1) "Translate and Localize", you then will see "TRANSLATE" tab (near the top) in /admin/structure/menu/manage/main-menu/edit (for the main menu, for example) and can now translate each link from the "translate" column (right-most?) at /admin/structure/menu/manage/main-menu.

Now, there are more than one option, entirely depending what you want to achieve on the menu.  For example, suppose there are a node "Hello" and its French translation node of "Bonjour" (they are two different nodes, say, nodes 1 and 2, respectively).  Would you like to provide the two links for both "Hello" and "Bonjour" in the menu (when viewed in either language)?  Or, would you like to provide the link for "Hello" for the English mode/readers, and that for "Bonjour" for the French mode?  (Such is the complexity of multilingual sites...)

Suppose you prefer the second option.  As an example, prepare a single menu link for "Hello/Bonjour" in the main menu; that is, the plan is, "Hello"-menu linked to "Hello"-node(=1) appears if viewed in English, and "Bonjour"-menu linked to "Bonjour"-node(=2) appears if viewed in French.

First you create the "Hello" menu link, linked to node 1.  Second, via the above-mentioned "TRANSLATE" tab in /admin/structure/menu/manage/main-menu/edit, you input the translated title as "Bonjour", and don't forget to change the link to Node=2 to make "Bonjour"-menu correctly point to the French "Bonjour" article.

Now if you view a different French node ("Au revoir" for example) in French (the path-prefix must be /fr/), you will see the menu of "Bonjour", which is linked to the French "Bonjour" node.  If you see its English translation ("Good Bye") in English mode (the path-prefix must not be /fr/), the menu above is "Hello", which is linked to the English "Hello" node.  Job's done.

The thing is, I think it is simpler to set the path-aliases for each content (a single path alias for a set of nodes for all the translations), and basically to give up using the form of node-type links like /node/2 entirely.  In the above-mentioned example, say, suppose you set the path-alias of artilce/hello for the node 1 (English; don't set a different path alias for the node 2, French, as it would add a confusion).  Now by accessing /fr/artilce/hello, you can see the node of "Bonjour" with the French menu.  However, if you access /fr/node/1, what you will see is the English "Hello"-node(=1), while the menu above is French one "Bonjour".  It is because the node=1 is written in English, while you are viewing the content in the French environment, which forces the menu to be in French (if you have enabled localising, other parts like user-menu become also French, but not the main content).

For some people, that may be what they want.  For example, a French shopping site may offer an English interface for shopping-basket etc, while they can't be bothered to translate the description of each item to sell.  I am guessing that is why the i18n in Drupal is designed like this.

Finally, you may want to "Flush all caches" frequently, while you modify the settings, to make sure any change you have made is reflected to what you see.