Most likely this issue:
iPhone abroad issue
As it says you may have to try many times before that works.
Toggling airplane mode on and then off and then quickly trying to configure the phone as outlined in that link may help to get this done quicker.
Blame Apple for the stupid way that they do things with iPhones unfortunately.
Hope this helps.
