Looked around and couldn't find a libnss-mdns that doesn't complain about perl dependencies, so I altered the debian version.

Install this after you install the avahi packages as such:

Restart dnsmasq just in case.

And now you should be able to resolve any other visible machine using .local as domain. Try by pining them.

If someone knows a repository where libnss-mdns is available please do share.

Good luck, let me know if I left something out.
Pete