Do you have WiFi and aGPS location reporting off? It could slow down position locking.
Sometimes my Nexus 4 GPS antenna hangs though, a restart and locking on via Maps helps for some reason, I use the app GPS Stats to see how many satellites the phone's seeing, but I guess you've done that. Maybe try out a tracking SW like Locus or something and see if the phone remains locked when moving for a longer period of time like going home from work, if GPS signal constantly goes away I'd recommend contacting Google on the issue. They'll either confirm to look into it or offer a replacement.