How does translation work

Menu translation depends of your menu items type.

Category, Content and product menu item are using their corresponding entity name/title.
If you want the label to be translated, you have to translate your category, your product or your content.

Block is not using label, but directly display his content.
You can duplicate your block and assigning it to the desired Store view, then translate it.

Page menu item label corresponds to the page “content heading” field. If this field is empty, the admin label of your item will be used instead of. Translate the page by duplicated, assign it to another store view and change his “content heading” field. If you feel Magento Page is poor with translation feature, we suggest to create a content type called “Page” to replace this feature.

Custom and node are not linking to an entity. The admin menu item label is used as the label in your menu. The label is parsed by “$this->__()” function, that will find a translation in your files for the label. Learn how to add a translation on your files : http://www.magentocommerce.com/knowledge-base/entry/custom-translations