Você deve ter o GNU Recode 3.5 ou superior instalado em seu sistema. Você pode baixar o pacote em » http://directory.fsf.org/All_GNU_Packages/recode.html.
A biblioteca Recode versão 3.6 adiciona caracteres estranhos atrás de strings convertidas sob certas circunstâncias. Portanto, é mais seguro usar o Recode v3.5 ou uma das alternativas disponíveis como a extensão iconv ou mbstring.