Well, I am unsure about what you mean by properly encoding them.

Then you very probably haven't. Please read the Perl Unicode Tutorial at http://tnx.nl/perlunitut and update your program. Perl's unicode support goes much deeper than just allowing byte strings, and typically means you have to change your input and output routines.