Originally described my problem in http://drupal.org/node/341993#comment-2389072 but since a patch was already committed on that issue I guess this problem needs a new issue.
If you have:
1. a multilingual site, I18n installed and language negotiation set to "Path prefix with language fallback"
2. a taxonomy vocab set to "Localize terms. Terms are common for all languages, but their name and description may be localized."
3. HS enabled for that vocabulary: "Use the Hierarchical Select form element for this vocabulary"
4. Use a language other than the default to create content, or administer the vocabulary
HS fails to retrieve terms correctly.
Currently my default language is english (no path prefix), if I switch to french to administer the vocabulary the terms do appear in the HS widget preview, until it is clicked on - they then disappear and the selection list is empty.
When creating a new node in english HS works perfectly for the configured vocabulary. If I switch to french the selection list is empty (the terms *do* have translations available).
There are no errors thrown either in drupal or firebug, so it's hard to tell where this problem starts, but I'm guessing it's the client side js since the terms do appear in the widget preview on the vocab admin page.