Quick solution: WAIT (1-2 hours) and manually register the SIM with the Mobile Network (AT&T, Viettel, olleh, etc.) in Settings section.
I had this problem when traveling from Vietnam to Korea. My SIMs worked fine in Vietnam, I had 2 of them and both didn’t work when I brought them to Korea, 1 SIM was registered and 1 SIM was to replace the old one which I had been using for years (I wanted to upgrade this one to 4G/LTE compatible version).
Both showed the same erroneous message: “SIM not provisioned”. The phone Mobile Network also showed that the Mobile Networks in Korea (e.g. olleh) are “forbidden”. After doing some research on the Internet, I realized it is not hardware but software problem, and I might not be able to use both SIMs as I have to register them with the Mobile Networks here – which I’d give up.
Luckily after letting the SIM inside 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 solution that seems feasible to me, don’t mind trying to “fix” the SIM, it’s fine, give it some hours to be registered. In my case I had to manually register it with the network (in Settings section) after the wait.
Good luck.