Why doesn't ECS Service Connect register new services properly?

I just started using ECS Service Connect and I'm seeing some weird behaviour. I have a cluster with a "web" service that handles all the incoming requests, and a couple of Rails services (App-A, App-B) that actually process the requests. If I create all the services at the same time (web, App-A, App-B) they all seem to communicate with each other without any problem.

The problem starts when I create the web and App-A services first and then wait a while (>5 hours) to create App-B service. When that happens, the web and App-A services talk to each other without any problem. However, the web service cannot see the newly created App-B service. Running ping from the web service to App-A works fine, but trying to ping App-B gives me a ping: bad address 'app-b.local' error.

Am I imagining this problem? If I re-deploy the web service it can see both App-A and App-B services just fine. It's almost like the web service doesn't update it hosts file or something but the reboot forces it to rebuild it somehow.