sorun tam olarak ne anlayamadım kusura bakma ama ben str_replace yerine str_ireplace kullanmanı öneririm
örnek :

$bozuk  = array("ü","ş","ı","ç","ð","ö","þ","ý","Ý","ç","Ö","Þ","Ü","Ç","Ð","ý","İ","ğ","Ş","ü","ç","ð","ý"); 
$duzgun = array("ü","s","ı","ç","ğ","ö","ş","ı","İ","Ç","Ö","Ş","Ü","Ç","Ğ","ı","İ","ğ","Ş","ü","ç","ğ","ı"); 
$veri= str_ireplace($bozuk,$duzgun,$veri);