$altera tiene un elemento más que $caracteres. Quizás eso provoque algún comportamiento extraño.
Te recomiendo sustituir la cadena convertida a minúsculas. Así podrías simplificar la sustitución (ya no tendrías que especificar sustituir Á y á, bastaría con sustituir solo Á o solo á). Para hacer esto, basta con poner
Código PHP:
$mtitulo_url = str_replace($caracteres, $altera, strtolower($mtitulo_urls));
También te recomiendo emplear expresiones regulares:
ereg_replace("[^a-z]", "", $cadena);
con lo que eliminás de una vez cualquier caracter que no sea una letra
Con esto, el proceso queda más o menos así:
Código PHP:
$caracteres = Array("ç", "ñ","á","é","í","ó","ú","à","è","ì","ò","ù","ã", " ");
$altera = Array("c","n","a","e","i","o","u","a","e","i","o","u","a", "-");
$mtitulo_url = str_replace($caracteres, $altera, strtolower($mtitulo_urls));
$mititulo_url = ereg_replace("[^a-z-]", "", $cadena);
Creo que así es mucho más simple.
Agregué "-" en el patrón para no eliminar los guiones que en el paso anterior fueron sustitución de los espacios.
Saludos.