You may have already thought of these, but here's some things to consider:
1. Is all the linework (edges, junctions) connected? I ask as when I've run into issues like this with Network Analyst in the past it is because some of the linework is disconnected, though visually it looks fine. Run topology to check, with rules.
2. The "Search Distance" for a facility to find the linework sometimes fails to find a nearby line, even though it is within the set distance. As a workaround, to insure it does, digitize linework to connect your facility point directly to the network (and then run topology on both the linework with your facility points participating to insure it is connected).
Hope this helps,
Chris Donohue, GISP