Quick solution: wait 1-2 hours, then manually register the SIM with the mobile network (AT&T, Viettel, olleh, etc.) in the phone's Settings.

I ran into this when traveling from Vietnam to Korea. My SIMs worked fine in Vietnam. I had two of them: one already registered, and one meant to replace an old SIM I had used for years (I wanted to upgrade to a 4G/LTE-compatible one). Neither worked in Korea.

Both showed the same error: "SIM not provisioned". The phone's Mobile Network settings also listed the Korean networks (e.g. olleh) as "forbidden". After some research I realized it was a software/registration problem rather than hardware, and I almost gave up, assuming I would have to register both SIMs with the local carriers.

Luckily, after leaving the SIM in the phone for 1-2 hours, the VinaPhone SIM started to work. I am doing the same with the Viettel SIM now.

So far this is the only workable solution I have found. Don't bother trying to "fix" the SIM; give it a few hours to be registered. In my case I also had to select the network manually (in Settings) after the wait.

Good luck.