MySQL - Reemplazar caracteres con stored procedure

Hola Gente, desde hace un par de dias que estoy con esto y no le encuentro la vuelta. Hace un tiempo desarrolle una funcion que llama a un procedimiento realizado en una base de datos mysql. Esta recibe como parametro un nombre y el procedimiento se encarga de analizar el nombre y buscarlo por parte en una base de deudores. Por ejemplo, para el nombre Juan Perez buscara en la base con el siguiente SQL select * from Base where nombre like '%Juan Perez%'. Si no lo encuentra ejecutara otra vez la sentencia SQL pero con '%Juan%', sino lo lo encuentra comenzara al reves, buscara primero el nombre completo y luego buscara solamente "Perez".- De acuerdo al registro encontrado (si coincide exactamente con el nombre) sacara un promedio que indicara si el nombre coincide el 100%, por cada busqueda extra este promedio disminuye.
El problema es el siguiente, no funciona bien con los nombres con "ñ". Asi que lo que estoy intentando hacer es cuando el procedimiento recibe el nombre, recorrer todo el string buscando una "ñ" si encuentra alguna reemplazar este caracter por otro (cualquiera de estos %,?,_,etc). Estoy trabado en el reemplazo del caracter. Recorro el string con un while, si encuentra una "ñ" determino la posicion en el string pero nose como reemplazarla.
Esto es parte del codigo que uso.

Set Nombre=Cancat(Trim(nme), '?');

La variable nme contiene el nombre a buscar. La variable Nombre es la que guarda el nombre modificado y lo uso para hacer la buisqueda por las bases de deudores.
El nombre no puede ser modificado desde la aplicacion por que a esta base convergen programas realizados en diferentes lenguajes (visual basic, c++, php, clarion) asi que si o si tiene que ser reemplazado durante el procedimiento.

Lo que debes hacer es:
UPDATE nombre_tabla SET campo_a_modificar = REPLACE(campo_a_modificar,'ñ','_');

Cuentanos como te va