I can definitely see what you are saying. My issue seems to be a loop where it gets stuck "Searching..." until I turn everything (wifi, cellular, etc.) off, reset the network settings, and do a hard reboot on the phone. I only occasionally get the "No service" message in the top corner.
My issue appears to be more in line with the one outlined here: http://brianmorristech.com/?p=1007
That said, I was really hoping that there was enough of an overlap between the two issues that the update would fix the connection issues and that the same bug was affecting the "No service" and "Searching..." errors. I've stuck with this thread because it has stayed active and I've found the members here aren't as dismissive as they are on others, which I really appreciate.
I do, however, think that there are several different issues that posters in this thread have expressed. Some are undoubtedly the exact issues that you had with the "No service" error, where others, like mine, are slightly different. Hopefully, most are fixed with this 6.1 software update.
Again, I appreciate everybody's help and at this point I am willing to chalk this one up as a fluke hardware issue. I've had good experiences with Apple in the past, and can understand that there will always be a few handsets that don't work perfectly, no matter what company produces them.