None of these worked for me. I reopened the phone and ensured the battery and antenna were properly placed, the cover degreased, the shield properly placed, etc. I had fixed the date/time, reset the network settings, restored iPhone from iTunes, left it connected to iTunes, tried toggling via WiFi and airplane mode. NO DICE.
HERE IS WHAT WORKED:
I chatted online with my carrier (AT&T). They had me read a couple of settings from my phone and sent a reset signal. BAM! Service.
If all else fails, but before fooling with your mother/logic board, contact your carrier.