Double check and ensure everything is connected (zoom way in if you need to) and make sure you have endpoint and vertex connectivity. I've also had an issue where I make a new feature as part of an existing feature class, but because it has no length, it doesn't compute as an edge on which to travel. So you may try calculating feature length and see if that helps. I think for my project, I just ended up editing an existing line and reshaping it to connect to a point off the line, but that probably wouldn't work in your case.
