Perhaps next you could try using the identify tool to progressively find a path of adjacent elements from your starting incident to your destination facility. If there is truly no valid path (which the solver suggests), then perhaps you will see where any potential connectivity problems are coming from.
If this does not help at all, then, if your data is small enough, perhaps you can zip it up and post it here for further review. I will warn you, however, that there have been problems with opening up attached .zip files on these forums, and I don't know when these will be properly addressed, so it may end up being a wasted effort.
If all else fails, you can always report the issue to ESRI technical support. They can work directly with you to look at your data and help you figure out the source of the problem.