I'm relatively new to Perl so one of the monks may have a better idea but have you tried using Encoding::FixLatin, I've recently used this to fix similar encoding issues.