Ma perché usi $HTTP_GET_VARS? E' assolutamente deprecato il suo uso ormai...
Usa $_GET! Il codice comunque sembra corretto... sicuro di non sbagliare da altre parti? Sicuro che la variabile sia piena?

Fai un esempio pratico e vedi se funziona (ma funzionerà sicuramente)
Codice PHP:
$var = "prova 1 2 3";
echo str_replace("prova", "test", $var); 
Dovrebbe stampare: test 1 2 3