From my experience this is caused by badly connected roads.
I used to get the error 75% of the time when routing home from work. After fixing almost all the errors on the routes I take home I get the error 5% of the time.
Take a look at the route in question and fix any errors. Most common error is continuous roads that are not actually connected in the map editor despite looking fine in the Live Map.
iPhone 3GS - OS 3.1.2 - Jailbroken
1999 Toyota 4 Runner
Houston, TX - Area Manager