Cambiar el imei no es ilegal, ni puede serlo, si el movil es de tu propiedad, lo que si seria es que se quedara otro sin que su movil funcionase por causa de estar usando tu su imei, o utilizas el nuevo imei para piratear las conexiones de otro, acurdate del protogoco gsm, en donde el imei se utiliza para autenticarse, al estilo de la ip en internet o en una LAN.
Un Saludo
PD: Creo que son ilegales los sistemas que te permiten cambiar el imei en España, por tal motivo deve se que no se encuentran facilmente.