Mucho más sencillo que eso. Mira este ejemplo, en vez de usar str_replace usaremos preg_replace
Código PHP:
<?
$origen=array("/¥/","/§/");
$destino=array("ñ","í");
$sql="INSERT INTO empleados (nombre,apellidos, direccion, municipio, cp)
values ('".preg_replace($origen,$destino,$reg['NOMBRE'])."','".preg_replace($origen,$destino,$reg['APELLIDOS'])."','".preg_replace($origen,$destino,($reg['DIRECCION'])."','".preg_replace($origen,$destino,$reg['MUNICIPIO'])."','".preg_replace($origen,$destino,$reg['CP'])."')";
?>