Taxonomy is normally pretty simple by default except that it's also called vocabulary (but never terminology although the tags are called terms) and that it can be attached to nodes as fields (using Content Taxonomy Fields to make CCK fields which gives you a bit more control) or not, or both.

Adding language makes it complicated though. Drupal can be said to support languages other than English, multiple-language sites, internationalization and translation. But it's not always user friendly or clear even to developers. Such is the case with taxonomies.

Let's say you have a site that's in two languages, English and Vietnamese. You have translated the interface of the site as well as nodes so that URLs are consistent. To switch language you just add the language code to the front of the URL. So you have a taxonomy with terms in your site's primary or default language. But you want to use the same terms by ID rather than a different set of terms.

1) Edit the vocabulary. Set "Localize". This doesn't set a language to any terms or anything, they are just assumed to be in the default language already.

[Look in term_data and confirm the language column is still empty.]

2) Refresh strings in Translate Interface. Now if you search taxonomy for a term it should appear.

[Look in locales_source for location = "term:$termid:name" where $termid is the tid of a term in your vocabulary. This means it's ready to be translated. After translating, it should be in localtes_target with the same lid. But the translation column is a blob so you won't be able to see the translation directly depending on your mysql client.]

3) I recommend installing the Translation Table module instead of searching for each new term in the regular translate interface. Translation table shows up as a new tab in the translate interface and you can select a vocabulary to see all of its terms in one place.

4) If you use terms in arguments in URLs you'll need something further. Otherwise, all URLs will use the term in the site's default language.

5) One last thing: Don't use t() to translate a term. Use i18ntaxonomy_translate_term_name on a term object (like if you get a vocabulary object from taxonomy_get_tree).