FWIW, I had a similar experience in Seattle on Sunday morning (October 23). Note that I'm a new user of Waze, and this is the first time I'd used it in downtown Seattle. Anyway, the disconnect was on I-5 in both ways between the north edge of downtown and the University district, which is probably the most heavily traveled section of highway in the entire state. Odd that this is where Waze would get lost...
I've also seen the "Proceed to highlighted route" message with constant recalculation when the first segment of your route is a long segment - it keeps trying to recalculate your route until you get to your route's second segment, and if getting to the second segment requires a turn, it doesn't get announced. I also noticed this happens every time you start on a longer segment. It probably happens on every first segment but is more noticeable when the first segment is longer.
I'm having the same issue for about the past week traveling on major interstates parts will cut out (side roads are still their) I will be driving on the road highlighted but it will just continue to say proceed to highlighted route. I have had people watching me online and their map is fine ive tried refreshing area maps etc with no success. Hope theirs a fix soon routing is worthless for me right now.
Forgot: iPhone 4S 6.0.1 waze 3.5.1 also occurring on my Nexus 7 however I rarely use it for navigation.