I just returned from traveling and thought it was only me until reading this post. I was in Vermont and Quebec when I had trouble. It started working yesterday.
Here is what I found by experimenting in case anyone is curious.
The problem was in the routing when multiple routes were possible because...
-it would still tell the distance when returning search results, but would not give trip-turn directions
-once I got close to the destination, it would begin working and give directions
So it knew my location but couldn't give directions.