Hello Aaron.
First, make sure your new roads are actually snapped to the existing roads. If there is even a tiny gap, they will not be connected in the network.
Next, check your network's connectivity policy. If the connectivity for your streets is "End Point", then the new streets must snap to end points of the existing streets in order for them to connect (and the Integrate tool won't help here). If you want your new street to be connected in the middle of an existing street, then you need to split the existing street, and also be careful to fix any attributes in that existing street feature that might have gotten messed up due to the split.
If your connectivity policy is Any Vertex, then then streets don't have to touch at end points, but there does need to be a vertex on the existing street at the location where the new street touches it. However, the Integrate tool should have taken care of this, so I suspect that the problem is one of the others I mentioned above.
To learn more about network connectivity, please read this page in the doc: ArcGIS Help (10.2, 10.2.1, and 10.2.2)