Most likely, what you have is not encoded in the character set you think, then.

I found Text::Unidecode to work pretty well, provided that its input is correctly encoded UTF-8.

I recommend that you start with explicitly encoded strings and see if these work for you:

#!perl
use strict;
use Text::Unidecode;
my $str = "\N{LATIN SMALL LETTER A WITH ACUTE}\N{LATIN SMALL LETTER C 
+WITH CEDILLA}\N{LATIN SMALL LETTER O WITH GRAVE}";
print unidecode($str);
# aco
[download]

If that works for you, you can now take slow steps in the direction of reading data and properly calling Encode::decode() on it, while trying to find the appropriate character set(s) that the data is provided in.