Nexus 4 getting "No Service" until a reboot after losing signal
I've solved part of this issue; switching to Airplane mode and back (bring down the status bar, go to the quick settings panel, tap airplane mode twice) DOES restore signal if you're in an area with signal. So there's that at least, but it's still losing signal until a forced update. You might have to wait a second between the first and second tap of the Airline mode button to make sure it activates (the airplane icon will appear in the status bar).

Also note that occasionally it seems the phone will actually still get a 3G/4G signal and a stable internet connection...while still displaying the "no signal" icon. The only way to know this is happening is to try and use online features and find them working. You might just want to do the Airplane mode trick anyway since it's quite confusing to have the no bars icon but have the internet and calls working (and of course in this state you won't notice if the signal suddenly drops again).