Claro es que para sustituir varias palabras, le debes pasar arrays a str_replace, no strings.
Código PHP:
$i = 0;
$lib1 = array();
$lib2 = array();
while($rowNot = mysql_fetch_array($sqlconsulta)){
$lib1[$i]= $rowNot["originales"];
$lib2[$i] = $rowNot["sustitucion"];
$i++;
}
$resultado = str_replace($lib1, $lib2, $noticia);
echo $resultado;
No lo he comprobado, pero así debería funcionar.