Drupal 7 menu translation and url aliases
Setting up a menu per language (as stated in other answer) seems to me more like going around the problem rather than fixing it. I created an issue for it at https://drupal.org/node/2051041 and attached a patch.

Using that patch you don't need to the unnecessary hassle of setting up tons of menu items per language just because the href doesn't render as expected.