Hi Tiffany,
I know you've been back in touch with Esri Support Services, I just want to make sure that others who find this thread get this information as well.
The new routing service requires a token from ArcGIS Online which the current versions of the ArcGIS for Local Government applications don't support. We are aware that the current service will be retiring soon, and are working on versions of our apps that will work with this new service. For now, though, you'll need to stick with the provided routing service (or possibly your own).
As you heard from ESS, you are seeing this routing error for some addresses because they aren't on roads known to the routing service. To get around this, you could try using your own routing service. I haven't tested this application with a custom routing service, but I don't see a reason that it wouldn't work.
-Allison