Well you want to use i18n taxonomy and have nice site, that is optimized for SEO and for viewers. Well you will have problems, here are some solutions depending on the which type of multilanguage option you choose for your taxonomy
1. Solution is to have terms localized, then you can manually make URL's for all of your languages and their taxonomies, because if you don't you will have one alias for them all. You can also try this module drupal.org/project/pathauto_i18n_taxonomy it should bulk create your aliases, you should setup all of your patterns to [term:i18n-vocabulary]/[term:i18n-name] for example and the delete old aliases and then bulk update new ones. This should work.
2. Use Translate option, then you will have your aliases translated, and everything should work fine but you will have all of your terms listed in the same list, so when you choose your term in dropdown and you have many terms this will get overcrowded and
not an elegant way to choose a term.
3. Use separate taxonomies for each language, there is a problem when you choose your term, if you are using english interface (/en) and you are editing french taxonomy no hierarchy will be shown and you need to switch to (/fr) to add your node to proper parent/place in hierarchy. Also you can't use language switcher as taxonomies are not connected and you need to make custom lang. switcher if you don't want pages not found.
Also follow this thread http://drupal.org/node/290421 to see what is happening with this problem and possible solutions. In the end I would recommend 2 or 3 solutions as 1 will also work but then If you want to use breadcrumbs and i18n then you will probably have problems there and you are then better of with 2, maybe no.3 solution.