Hi all had same problem with iPhone 4S Vodafone
Which I previous jail broken if u have this problem remove sim card during it saying searching and wait go into your settings and change date time to manual and then automatic leave for few minutes turn phone off and back on once SIM card say not inserted then insert SIM card it will take around 30 seconds then will connect I had to delete Sam and ultra snow if jail broken as this bounces signal so easier if they are removed thank you all as this helped me