Yo creo que el problema es que envías la cadena codificada en utf8... prueba así:
Código PHP:
function sef($cadena){
$self=utf8_decode($cadena);
$sef = trim($sef);
$sef = strtr($cadena, "áéíóúÁÉÍÓÚñÑçÇ", "aeiouAEIOUnNcC");
$sef = preg_replace("/¡|¿|\?|!|\^|'|:|@|#|\$|%|\"|~|\+|\*|\/|\||\\|\[|\]|\(|\)|\{|\}/","",$sef);
$sef = ereg_replace("[.]", "", $sef);
$sef = preg_replace("/,/","",$sef);
$sef = preg_replace("/'/","",$sef);
$sef = preg_replace("/´/","",$sef);
$sef = preg_replace("/&/","",$sef);
$sef = preg_replace("/( - |- | -| )/","-",$sef);
$sef = preg_replace("/-{2,}/","-",$sef);
$sef = preg_replace("/^-|-+$/","",$sef);
return $sef;
}