My phone said "searching" today and never got a signal. I went to perform ANOTHER (had to do this 5 times to my NEW iPhone 4) reboot and now I cant get it going with wifi or wired directly to my pc. Nothing. Verizon's answer (not their fault) is to replace it. This will be my third in six months. Had a Blackberry for almost two years and not a single problem. iPhone is riddled with them.
Try resetting network settings. Settings / General / Reset / Reset Network Settings. Also if you have a case, try taking it off to see if there's any differences in signal. If there is a difference, case is causing it.