It would have been helpful to post some of your code. In particular, suppose you try to create a really simple, minimal script that prints accented characters just fine on the terminal, but when you run it like this:
perl test_script.pl > test.txt
and look at test.txt, those characters are messed up. Then we could look at your code, and even run it on different machines, to give you more useful advice.
It probably makes a difference where those accented letters are coming from (some other input file? hard-coded in the script?) And what version of perl are you using?
