tarjeta sim no es compatible

Tengo un iphone 4s 32 gb. Comprado en Venezuela en dic del 2011. Me he venido a vivir a España y lo quiero usar aca. Tengo otro movil con Orange y quisiera utilizar el iphone con mi linea orange y al meter la tarjeta sim me dice que no es compatible. Pense que mi iphone estaba liberado para cualquier operadora , pero al parecer no. Que puedo hacer ? He comprobado por iphoneimei y me sale SIM LOCK: Check sim lock. Fui a orange y no tienen conocimiento. Debo ir a una tienda APPLE? Ya por medio de itunes, restaure el tlf, se quedo colgado y no me quedo mas q hacerlo, por suerte habia guardado todas las fotos en el ordenador semanas antes. Por lo que quedo de fabrica. Que puedo hacer para utilizar el tlf con cualquier operadora? gracias