I have the problem on my 16 GB black nexus 5 with stock Rom and no root. I tested with dalvik and art but the problem exist. I have found 3 solutions:
1- reboot phone (temporary solution)
2- stop Google Play Services (temporary solution)
3- uninstall updates of Google Play Services use with stock/no update (permanent solution)
one more thing; when I can't get a location fix with network/wireless GPS mode on Google Maps or any other application, I can see a circle on " Yandex Navigation" that shows my location.
but more interesting thing is I can see a circle that shows my location on Yandex Navigation when my GPS is completely off.
I think this problem is about Google Play Services or Google Location Services. I hope someone find a solution.
Reboot was the one I used to fix it, didn't know about the others you found.
In a strange way glad to see it's a software bug, which means it's fixable. I guess the friend I mentioned has not updated the Play services ever, that would explain why he is not affected.