Perl: warning setting locale failed en Ubuntu Linux

En uno de mis servidores de prueba, encontré un error bastante extraño y que en verdad me tomo tiempo encontrar la solución, al ejecutar casi cualquier orden en la linea de comandos, salía algo así:

La solución es simple, solo hay que ejecutar los siguientes comandos como root, o con sudo antes:

Para verificar la solución, solo hacemos un: