I have an iPhone 3GS OS 6.0.1. and I’m traveling along and it takes a few seconds (sometimes minutes) for Waze to catch up with me. Also, if I try to report anything I get the No GPS Connection error message.
Resetting my Network Settings helped temporarily. I have contacted Waze and I am still waiting for a response.
Have you also done a full reboot (press and hold home and lock buttons)? Once a month or so I run into GPS problems and that is the only thing that works for me.
Same setup here, usually no problem. Once in a while I see those symptoms while I am traversing a border and the iPhone gets in a kind of “undefined state” while switching between networks. Sometimes it recovers itself after a minute or so, sometimes it is enough to disable 3G-reception and sometimes I have to reboot. But all this is always RARE.