Alright I just resolved the problem with my iPhone 5 a few days ago. It hasn't been working for close to 3 weeks with the infinite "searching..."
1.Soft Reset your phone. If that doesn't work,
2. Remove SIM card
3. Restart phone (if it still says searching while SIM is removed skip to step 6)
4. Reinsert SIM and turn the phone on (still not working?)
5. Update iOS.. Yes I know it sounds so predictable, but it has helped in the past.
6. If all else fails, grab a charger and use the "Restore" feature on iTunes. After repeating step 6 twice, my phone started to pick up cellular service again allowing me to complete setup.
Best of luck :)