Yet another interesting multi lingual challenge, this one related to taxonomies. The reason for your issue might be because of one reasons explained below.
Use a recent i18n version
Make sure you're using that the version of the i18n module is at least version 7.x-1.8, because it might be because of a bug in the 7.x-1.7 version of it.
Use the correct translation mode
You also want to check the "translation mode" that you've specified within admin/structure/taxonomy/categories/edit (whereas "categories" is the name of your specific category): by default that is set to "Localize", though it should be set to "translate". Attention: after changing this value, be aware that you then also have to:
- enter a translated value for each of the tags and
- revisit any of the existing nodes that are already using the specific taxonomy, so that they use the (translated) term that corresponds to the language of the node.
Obvious, if you have other taxonomies with the same issue (like "categories" in your case), you should repeat this for those others also.
Consider the Title module
Possibly related to this issue is that titles that do not get translated in a site using the i18n module, is most often because of the Title module that has not been enabled. From the module's project page (bold markup added here):
After enabling the module as usual, visit the Manage fields page of the content type, taxonomy vocabulary or "comment type" which you wish to replace fields of and click the replace link. That's all.
FYI: I have not yet run into any situation where I had to install/enable this module to get multi language site to work as I want.