Además del PIN, debes de tener con la documentación que te vino con el teléfono (con la tarjeta concretamente) un código llamado PUK
Aunque el PIN lo cambies, con el PUK puedes recuperarlo
Creo que el problema lo tiene con el PIN que ha puesto al propio teléfono, no a la SIM