I had a similar problem just south of Barnards Loop lately. I was trying to go a certain destination, and all I got was "route unavailable". So I tried some systems a bit closer which worked fine, and then did the last jumps "the old way" (manually).
I believe when stars are getting pretty sparse, that the route planner is trying to go in the straightest line possible towards your destination. When confronted with a route that makes it go a bit "back" it flips out and refuses to comply.
Other thoughts on this is appreciated.