This sounds to me like you have (temporarily) lost internet connection.
In my experience the new route is calculated usually in less than 5-10sec - even if internet quality is only Edge.
If you could take a screenshot of such situations it might help the developers to solve the issue.
In very rare occations I had similar observations.
The pattern seems to be many routing calculations in a row without following the new calculated route, but take another one instead.
Automatic recalculation was on btw.
After this I stopped navigation and calculated a new route:
Only after restarting the App it continues to work as expected.
Btw:
These screenshots had been taken on my old Galaxy Nexus with Android 4.3 and I was never able to reproduce this. Now I have a new phone.
Edit: My issue was with older Kurviger version (have a look at the date of the screenshots)
Manfred