I am an iPhone newb, right off the bat, so excuse me if this sounds stupid. I had the same problem where I get the "No Service" text in the top left. I kept pressing the power button to turn the phone off, but when I would turn it back on, the problem wasn't fixed. Finally, I read the instructions that come with the phone (amazing, I know). Turns out, to actually turn off your phone, you have to HOLD the power button for a few seconds, not just press the button once. I guess that's a sleep mode (again, yes, total newb...iphone wizards are probably loling at me right now 🙂 )
Once I did that and turned it back on, I had perfect reception.