Zaxo's guess is mine too. Try printing every line as you go. Check what your LANG is set to and what enconding the file is in.

Did this work on a previous version of perl on your linux machine? Was that a pre-5.8.0 version?