Typical taxonomy translation issues
My best guess is that you are experiencing the typical taxonomy translation issues, as described in the community documentation about Taxonomy translation also. While digesting that, you may want to verify one of its comments, which is about using the Title module also.
The closest I have come so far with translated terms (and without using the Title module), is similar to the setup you have done so far. The result of it being that when you want to select a term from a taxonomy on a language specific node, you get a list of all terms to select from (with all terms from all languages). Not the ideal solution, but similar to what is written in the URL I mentioned, and probably "as good as it gets in D7".
Translate vocabulary name
If however you're only looking for a way to translate the vocabulary name (as the title of your question indicates), then be aware that that is simply not possible today, and is actually a known issue: Vocabulary Name value doesn't get translated. It dates from 2005 (!), related to D6, status "won't fix". However comment # 2 in that issue states:
I have used the locale module to translate the name of the vocabulary, and display it with t($vocabulary->name). If all modules would display the name this way (e.g. taxonomy_menu does it), then there is no need for a new database table i18n_vocabulary.
The t($vocabulary->name) seems like a possible/partial work around to consider, i.e. from within a (custom) module.
There is a more recent similar issue, i.e. Vocabulary names are not translated. That one is for D7, with status "needs work".
Another potential work around could be to have a separate taxonomy for each language (and with a "name" corresponding to that language). Of course, you'd have to think how to best use these separated taxonomies for each content type (a kind of "solution to the problem, changes the problem) ...