How to get taxonomy translated when creating a new node in a different language than the interfaces?
Language Selecting

There are number of ways Drupal distinguishes which language the current user is in (yourself for example).

The admin page at '/admin/settings/language/configure' lists 4 methods.


None.
Path prefix only.
Path prefix with language fallback.
Domain name only.


As you can see, to determine the language, Drupal either uses a 'path prefix', 'language fallback' and 'domain'.

The path prefix is simply something like '/de/about-us-page'. Drupal sets the language to German. When I say set, I actually mean it sets it for that particular page request. Then visiting '/about-us-page' would NOT display the language in German but your default language (maybe English).

For Language Fallback, Drupal check if the currently logged in user has a language set in their $user account. If not, it will look for a language from the headers sent from the browser. If in any case the language cannot be determined, the default language is used; again may be English.

The Domain method is simply inspecting the domain and checking if it has been mapped to a language. e.g. German to domain.de.

Conclusion

From this, you can see that Drupal is simply reverting back to the default language. You setting the 'language' within the node edit form, is simply mapping this node to that language.
Usually when adding content for other languages, I switch into the native language. This ensure my taxonomy terms are mapped correctly.

Essentially, this is not a problem but the way this system works.

Possible Fix

If all the terms you are using are common to all languages, you can modify the Taxonomy translation mode to 'Localize' instead of 'Translate'. This should allow all the terms to be saved correctly even if you use the edit page without prefix 'node/add/page'. 
Just ensure you translate the terms using the String translation module.

Hope this help.
Amarjit