Podrias usar las entidades html en tus cadenas para que funcionara correctamente, ejemplo:
Código PHP:
$acentos = array("á", "é", "í", "ó", "ú");
$validos = array("a", "e", "i", "o", "u");
$cadena = htmlentities("Esto es un ejemplo: á - é - í - ó - ú");
$remplazar = str_replace($acentos, $validos, $cadena);
echo $remplazar;