Okay from reading through this thread you are not all experiencing the same thing. There are two distinct issues:
1) Losing signal which comes back again by itself.
2) Losing signal WHICH WONT COME BACK UNTIL YOU REBOOT THE PHONE
The second issue I had on a family members iPhone, I asked on these forums for help but didnt get one single reply. Oddly enough a search of the interwebz found that a lot of people get this problem, so maybe people on here arent as clued up as they claim to be
So I set out to fix it myself, and I did. I came to the conculsion that somehow the software/firmware that runs the phones cellular modem had become corrupt. Either that or the antenna had become faulty. Resetting network setting etc does not resolve. Neither does tweaking the carrier settings. Here is the only way I was able to resolve it:
1) Downloaded a fresh copy of IOS 5.0.1 to my PC.
2) Connected the iPhone to iTunes
3) Put the phone into DFU mode which prompts iTunes to tell you it needs to be restored
3) shift key and restore button in iTunes prompts you to specify the file location
4) Browsed to my freshly downloaded IOS file
5) Phone restored perfectly and is now fixed
If that hadnt worked there is literally nothing else to try and it would have gone back to Apple for repair. I also dont believe restoring the phone in the usual way (through iTunes or on the phone itself) would resolve the problem.
By putting the phone into DFU more you are absolutely restoring everything. Any other method does not restore the phone in the same way.
Good luck and let me know if it works to you too!