I have followed instructions in this knowledge article for sending email templates in recipient's language: 
https://help.salesforce.com/articleView?id=000120154&language=en_US&type=1

I have the language set in the messaging:emailTemplate tag based on recipient's LanguageLocaleKey:
<messaging:emailTemplate subject="Subject" recipientType="User" relatedToType="Object__c" language="{!recipient.LanguageLocaleKey}" >
Component reference for emailTemplate, 'language' attribute: "The language used to display the email template. Valid values: Salesforce.com-supported language keys, for example, "en" or "en-US". Accepts merge fields from recipientType and relatedToType."

.. and included custom labels into the template: {!$Label.test}

There is a translation for the language I'm changing to in my settings that I'm testing for. I've also tried with apex:outputText, apex:outputLabel, etc... and still I keep getting the custom label value in English (default language).

Any ideas what I'm missing?