Hola, acabo de solucionarlo, pongo la respuesta por si a alguna otra persona le sirve.
Usando el parámetro convert :
Código:
SELECT CONVERT(AES_DECRYPT(nombre,@password) USING LATIN1) AS nombre FROM clientes HAVING nombre Like '%xxxx%'
Saludos a todos