Data, but no cell signal

My phone has been working great for the last 6 months after a screen replacement. A couple of days ago, I noticed that I had no service when coming out of the parking garage, and now I cannot get any voice service.

I have entered field test mode, and I am getting -85 dBm from the antenna, so it does not appear to be a blue coil issue. To be sure, I looked under a microscope at the RF circuit and I could not find any missing components.

When I do a restore to factory defaults on the phone, I will have 4-5 circles of signal at the setup screen. As soon as the phone accesses the SIM card and tries to connect to the network, the circles are all empty. My carrier is shown at the top next to the circles, and I can access data just fine.

I have tried to manually set the date, reset my network settings, but to no joy.

I re-checked my IMEI on multiple websites and it is not black listed.

I got a new SIM card from the carrier, but that did not help. The SIM card in another phone works right away, so it is not an issue with the SIM itself.

Any ideas?

UPDATE: I am able to make calls, if I turn off all cell data. IF I disable only 3G, I still cannot call. Calling works whether wifi is enabled or disabled.