I would try pulling out and then reinserting the SIM card. I have not heard of this issue being related to SIM cards, BUT if it just started happening when you replaced the card THAT is the place to start.
CrackBerry is in no way Affiliated with BlackBerry. We take pride in our unbiased content, however do occasionally receive free products from vendors that we review or discuss. For more info click here.