Did you try plotting manually? It also fails when you have permit-locked systems in your way, it happened to me too. The only way then is to manually plot in smaller distances in your galaxy map, avoiding those areas.
It might fail because for some of the longer jumps you will need to take into account FSD injection, what goes over your jump range of 73ly for your DBX for instance. When I went to
Star One, the last 1,500ly of the trip, both EDSM and Spansh failed my route, so I had to manually plot that route in game, at the galaxy map.