While I realize that I am about 7 years too late to help you, this comment may potentially help someone else with the same issue so I decided to respond.
If this happens, take a look at how you set the problem up. My guess is that you set a variable to the wrong attribute, such as 'label' as Distance or Time Attribute, etc.
This could also be a problem with your roads data. Some datasets are better than others, and yours could have been of poor quality or a compilation of several datasets, resulting in some streets that don't quite match up or intersect like they should.
Third, double check the input data that everything is exactly where you would expect it to be. There could be conversion errors as you converted from file types or geographic coordinate systems etc.
I hope this will help someone else who has a similar problem!