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
> same.

##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.