Babelfish was correct.
Some Russian speakers write email subjects in translit (Russian words written with Latin letters), to escape these problems altogether. Even if you solve the problem on your end, you have no guarantee that the recipient will be able to read your subject line. For example, my school had its Exchange server misconfigured in such a way that Cyrillic letters in subjects turned into question marks when forwarded to external addresses.
Searching CPAN for 'Translit' yields several modules that look promising.
