Problema con tilde y PHP

[cnyx]

Pues el problema no se resuelve, utilizando str_replace he comprobado que sustituye cualquier letra correctamente excepto aquellas que tienen tilde. Lo curioso es que si le digo que sustituya las vocales sin tilde por vocales con tilde si que funciona. Alguna idea??

Gracias, saludos.

PS: respecto a la base de datos, como ya dije no puedo modificar nada.