Somes troubleshooting ideas:
If you haven't already done it, I'd start by running topology on all the participating datasets. Use rules to ensure that you have connectivity between all the edges. It's been my experience with network analysis that there can often be very small gaps between the edges that throw the analysis, even though visually the lines look connected even when zoomed way in.
One rough and dirty way to check for this without doing the topology is to run a few Service Areas at several distances. If you notice the Service Areas not covering areas with linework (edges) at the expected distances, that points towards issues. It may be a disconnect is present, or that some of the edges have a directionality error (set one-way when they should be two-way, or set opposite the direction they should be).
Another potential issue - be aware that the Search Distance sometimes will fail to find nearby edges, even when they are within the set distance. In this case, you may have to digitize in added linework from your existing edges to the points to ensure a connection. Be sure to check the topology of whatever you added.
Chris Donohue, GISP