Here is how I fixed it easily.
we have Verizon. We went to Europe and got new SIM cards for Vodaphone. As soon as I put in the new SIM a message came from vodaphone that had me download a new profile to my phone for me to be able to use that SIM card. You need to remove that profile and magically it works.
To remove the profile at least on iPhone go to settings then general then go down and right after VPN look for Profile. Click on it and remove this profile. Now you need to reset the network settings so in the same area go down to reset and click reset network settings and you will be back to business.
hope this works.