Oddly enough my device began having a hard time around the time I updated to Maps 8.0. Now I've got to drive for a good ten minutes before Maps appears to catch up with where I am. In NYC ten minutes on a route can throw me the heck off from getting to work on time big time.
Restarting the phone, turning off and on GPS, removing Maps from the recent apps list, clearing its cache all seem to be hit or miss when it comes to regaining a reliable lock on where I am.