Isso parece um problema de perl. Versões mais recentes do perl não têm esse problema. Veja a saída do meu sistema:
$ perl -v
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
LANGUAGE = "en_US.UTF-8",
LC_ALL = "en_US.UTF-8",
LC_TYPE = "en_US.UTF-8",
LANG = "en_US.UTF-8"
are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
Isto é perl, v5.8.6 construído para x86_64-linux-thread-multi
Veja agora esta saída:
$ LC_ALL=C perl -v
This is perl, v5.8.6 built for x86_64-linux-thread-multi
Copyright 1987-2004, Larry Wall
Parece que o perl 5.8.6 não gosta da saída UTF-8? A configuração LC_ALL = C livrou-se do aviso.
Instalei outra versão do perl (5.18) e que funciona com a configuração UTF-8 sem nenhum aviso.