I a mseeing this issue as well. It seems to be a software issue. I took a shorty 40 minute trip a few days ago and it worked perfect. Then when I needed to come back 3 hours later, I set my home as the destination and Maps just kept saying "Follow the route... Searching for GPS Signal". I had the Gnex on my dashboard facing the sky, so line-of-sight was not a problem. After 10 minutes of allowing it to search with no success I gave up and rebooted the phone. Once it rebooted, it found the GPS signal almost as instantly as I pressed "Navigate".
To me it's clearly a software issue if a reboot resolves the issue. It's highly annoying.
Facebook
Twitter
Instagram