Código PHP:
<?php
$frase_original = "C";
$nueva_frase = str_replace("C", "Cualquiera", $frase_original);
$nueva_frase = str_replace("0", "Centro", $nueva_frase);
echo $nueva_frase;
?>
En la segunda tienes que cambiarlo en nueva_frase y no en frase_original.