My brand new iPhone 5s will randomly go to zero bars of service and stay there. Usually the only way I notice this is when I try to make a call and just hear dead silence for a minute. After this I'll look at screen and realize it has happened again. Rebooting the phone clears it up until it happens again.
I figured I just lived near a problematic cell tower, but this has happened at home and 35 miles away at work.