MENU items doesnt seem to get translated?

I might be doing some wrong, but here is what happens:

1) I have an English menu that I am trying to translate (content translation works just fine).

2) I search for the string, save it, then try switching language - nothing happens, menu item is still in English

3) Am I missing something, is it a bug? What should I do.

Thanks for any help!