I've contacted Salesforce support and here is what I got so far :
I have investigated and replicated this issue on my Winter'17 Dev Org.
I found that the custom label displays properly if the user language
is same as that of the custom label language.
If we change the language of user to some other language than that of
the custom label, we get this error.
This behavior is not happening in Summer'16 Org. Another thing I have
tested is that when translation settings are turned on, it seems that
the error doesn't happen.
I am escalating this further for Tier 3 attention. In the meantime,
the workaround would be to make sure custom label and user language is
EDIT 09-22 : update from SF Support
I have got an update from Tier 3 that this is a bug that has been acknowledged by R&D.
They are working on priority to release a fix which should get done by next week (safe harbor).
EDIT 09-29 : fix released
Salesforce seemed to have released the fix for that. My instance is working fine now.