Sim Card Locked after Apple Replaced Phone

Today I received my phone back from Apple via UPS. It appears they replaced the phone. I followed the instructions and removed my SIM before sending it to Apple. When the new phone arrived, I put my old card in it and it started to restore it. About every 5 mins, I get a Sim Card failure message or Sim Card locked message. The Sim Card locked message tells me to recycle the phone. I did that and keep getting the same messages. All call attempt show failed call.

What should I do? I didn't have SIM card issues regarding my repair. The replacement was a microphone issue.