C'è una cosa che non capisco.

Fai una select con una clausola where cioè selezioni soltanto alcuni record della tabella ma fai un update globale !!!! nel senso che aggiorni tutte le Description con quella in corso di trattamento !!!!
Per fortuna tua il replace che hai messo nell'update non rimpiazza sempre.

:master:

Se nella tua tabella vi è un identificativo univoco puoi procedere cosi...

codice:
$query = ( " SELECT Description, id FROM links WHERE ( Description LIKE('% $s_grave %') OR Description LIKE('$s_grave %') OR Description LIKE('% $s_grave') OR Description LIKE('% $s_grave, %') OR Description LIKE('% $s_grave. %') OR Description LIKE('$s_grave, %'))") ;
..
while (list($desc,$id) = mysql_fetch_array($result)) {
 echo "$desc";
 $ungraved = array($s_grave);
 echo "
$ungraved[0]";
 $graved = array($c_grave);
 echo "
$graved[0]";
 $new_desc = str_replace ( $ungraved[0], $graved[0], $desc );
 echo "
$new_desc";
 $query1 = "UPDATE links SET Description = '$new_desc' where id=$id)";
 $result1 = mysql_query($query1);
 if (mysql_affected_rows($result1) > 0)
  echo "
I dati sono stati aggiornati correttamente
";
 else
  echo "
I dati non sono stati aggiornati
";    
}