Ich weiß ja nicht, wie hier auf die Excel-Datei von Perl aus zugegriffen wird, aber meine Intuition sagt mir, dass es sich um ein Zeichensatzproblem handeln könnte.

Hast du schon mal versucht, die Spaltennamen in verschiedenen Kodierungen zu übergeben? Insbesondere würde ich mal die Windowszeichensätze und die UTF-Varianten durchprobieren.