Que va he probado eso y sigue sin cambiarme bien las tildes, no sé el motivo...
 
Al final he probado otra cosa y me funciona, no es la mejor solución...pero ya llevo mucho tiempo perdido con esto.... 
Os lo pongo por si a alguien le sirve:  
 Código PHP:
    <?php
function urls_amigables($url) { 
 
// Tranformamos todo a minusculas 
 
$url = strtolower($url); 
$url = htmlentities($url);
//Rememplazamos caracteres especiales latinos 
 
$url = str_replace ("á", "a", $url);
$url = str_replace ("é", "e", $url);
$url = str_replace ("í", "i", $url);
$url = str_replace ("ó", "o", $url);
$url = str_replace ("ú", "u", $url);
$url = str_replace ("ñ", "n", $url);
 
// Añaadimos los guiones 
 
$find = array(' ', '&', '\r\n', '\n', '+'); 
$url2 = str_replace ($find, '-', $url); 
 
// Eliminamos y Reemplazamos demás caracteres especiales 
 
$find = array('/[^a-z0-9\-<>]/', '/[\-]+/', '/<[^>]*>/'); 
 
$repl = array('', '-', ''); 
 
$url3 = preg_replace ($find, $repl, $url2); 
 
return $url3; 
 
}
?>    
  Muchas gracias por las respuestas. Un saludo