Sometimes my GNex glitches with the GPS and states no GPS as yours does. I just leave Waze in the background, open Google Maps, let it lock on to my position, then return to Waze. This has fixed the issue every time. It has only happened about 5 to us to me though.
~I don't always respond to the forums from my Nexus 7, but when I do, I Swype with Tapatalk 2.
Southwestern Pennsylvania My Waze idea: Vote Here Pls!