If the Service Areas look reasonable when you're optimizing for distance, my guess is your network connectivity is fine. If you had a connectivity problem, distance-based analyses would also look incorrect.
Rather, it's more likely there is a problem with the way your Time impedance attribute is configured. You should take a look at the cost attribute. Do the units agree with whatever field you're drawing from, if you're using a field evaluator? How the evaluators are configured, and does it seem correct?