Antes de nada decirte que te estas saliendo de rango en el bucle que haces, porque $linia vale 2 cuando en realidad tu solo quieres que te reemplaze $cadena[0] y $cadena[1], ya que $cadena[2] no existe...
weno a lo que iba, podrias hacer algo como esto:
Código PHP:
$cadena = array ("nicolas se va al parque","parque");
$linea = count ($cadena);
for($i = 0, $i < $linea, $i++){
$rem = ereg_replace ("parque","circo",$cadena[$i]);
/* la funcion ereg_replace devuelve la cadena modificada, si no hay coincidencias que reemplazar, devuelve la cadena original */
if ($rem!=$cadena[$i]) echo "se reemplazo";
}