avahi daemon failing to resolve some services in RHEL 6

Issue

• We're starting to use avahi here for mdns resolution, and we are seeing some strange errors when browsing the network. For instance, if we do:

avahi-browse -rkt _ssh._tcp

We get some answers back, but then we get many hosts that timeout:

Failed to resolve service 'aaa' of type '_ssh._tcp' in domain 'local': Timeout reached
Failed to resolve service 'bbb' of type '_ssh._tcp' in domain 'local': Timeout reached
Failed to resolve service 'ccc' of type '_ssh._tcp' in domain 'local': Timeout reached
...