What have you actually replaced is it the phone or the sim card?.If you replaced your phone & stuck with the same network that your sim card was on?,then 9 times out of 10 it will accept your old card but it doesn't work all the time.I had this problem a while back when i bought a new o2 phone but for some reason it didn't accept my old sim card which was also o2 & i got a message saying insert sim card.