I get it too occasionally. Not sure. I've gone to the apple store and spoken to the Genius a few times. Every time they just blame it on AT&T's service. Which is a crap answer to me, but you can't get them to say anything else. I'd be pretty pleased if they'd swap me out for a replacement, but I can't get them to.
I know it is definitely not AT&T's service, since I am in Canada on Rogers' network!
On top of it, none of my previous phones (and I've had many) have ever had reception problems anywhere. Coverage is very solid in my city, even in basements.
I've done a software restore already. And the problem still happens. It doesn't happen that often, but even if I catch it doing it once a day, I could have missed a call.
And I don't have Navizon or Locate Me installed, but thanks for the tip.