I'm currently on a Samsung Note 3. The last few days, about a week or so, I've had trouble with Waze keeping in touch with GPS. Some of the time, I know it's not Waze's issue, as I see the GPS icon blinking, showing it's searching for GPS. But quite often, the GPS Icon shows it's still connected, but Waze shows the litle red icon showing "no gps", and it fails to guide me. As much as I LOVE Waze and Love the concept of crowd-sourcing, I've had to return occasionally to Google Maps, as I get no result from Waze.
While I've not tested this yet, could it be an issue where Waze can't share the GPS with another app? I also have a mileage tracker app that I run at the same time sometimes. I haven't been able to tell if the disconnect happens more often when I'm running both apps yet, but I'll do some research on that. Is that a possibility?
Waze gives the same message when there is no GPS at all, or when the GPS signal has an error bigger than a certain value. I've seen on my logs at least 1Km, but I'm sure it's less. So if your device has bad coverage, other apps will still show your approximate coordinates and a huge circle representing the error (assuming it's similar to iOS and even the Google Maps for iOS), whilst Waze will simply ignore those big-error coordinate device information samples.