Are you using any restrictions in your analysis? Perhaps the roads your routes refuse to travel on are restricted.
Does your network have turns in it? Perhaps particular turns through an intersection are restricted or have large delays imposed on them, which discourages travel there.
Maybe your network isn't well connected. Pick one of the intersections in question and use the Network Identify tool (from the Network Analyst toolbar) to click on the streets leading into that intersection. In the box that pops up, you'll see the edges and junctions that are connected to the selected road. If you click on them in the Network Identify window, they will highlight on the map, so you can make sure that all the roads that should be connected actually are.