quizás sea una estupidez, pero me gustaría hacer la prueba... A mi me funciona perfectamente la función str_replace. Pero cuando tengo que enviarle muchos valores genero una array, mejor dicho dos:
Código PHP:
$reemplazar = array(':)', ':(');
$reemplazar_con = array('<img src="happy.gif" />', '<img src="sad.gif" />');
Un saludo.