Fireeyeeian Unfortunately these symptoms sound consistent with a hardware problem.
I guess the best case would be something simple like junk on the contacts of the SIM card. You might try using a pencil eraser, gently.
The next-best case might be replacing the SIM card. Maybe not too likely, but maybe fast and free.
Though it would be disruptive, evaluating the health of the cellular modem might be easiest by wiping the device and flashing back to Google's OS. If you see the same symptoms then, the cellular modem may be bad.