I have had a complete nightmare with this. Initially just the "searching" problem. So I tried updating the time countless times. Tried the flight mode thing on and off. Tried resetting the network. All multiple times. Nothing worked. Then went to iTunes tried to do an update but it wouldn't work due to some error. And my only option then was to restore to factory settings which also won't work. I can't believe that just changing the battery myself has led to this. Really frustrating. And I'm now left with all my data lost and having to buy a new phone.