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
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
##EDIT 09-29 : fix released SalesforceSalesforce seemed to have released the fix for that. My instance is working fine now.