Buenas, yo también tengo una HTC Touch S y me pasaba lo mismo. Ni siquiera pudieron liberarla en una tienda especializada. Parece que Movistar lo complica más que otras operadoras. Cuando daba todo por perdido lo intente a través de
www.sim-unlocker.com y el codigo funcionó a la primera, eso sí, previo pago de 15 € (me pareció un precio más que aceptable después de todas las vueltas que dí) Espero que te sea de ayuda y ya nos contarás que tal. Un saludo