Comment 3 for bug 2021409

There's a detail in the github issue that wasn't noted here:
I have Ubuntu Server 22.04.2 running in a VM (VMWare 13.0.2) on an Apple Silicon Mac running macOS 13.4.

That makes the network driver situation less likely but the firewall situation still possible.

A few extra questions:
What kind of network is fusion set to - bridged, nat, host-only, etc
+ If you are using bridged, but to your macs wireless adapter, I have also experienced this not working as expected. Try use ethernet via a USB-Ethernet or native ethernet if your machine has it - and see if it works then. That was the case for me. If you google "vmware fusion bridge wifi" there are lots of posts with slightly different setups and symptoms.
+ If you are using nat/host-only I would expect only to be able to resolve hostnames with the host Mac and not the rest of the network

Run tcpdump as directed, I am curious if you see any packets sent from any other node on your network. I am guessing not. If you are, it would be ideal to capture a pcap file (a copy of all the network packets on 5353) from both this linux VM, as well as another linux machine on the network that is not the host mac:L

tcpdump -i <interface> -s 65535 -w lp2021409-$(hostname).pcap port 5353

Then run a query from both the VM and external host, for the other machine. While the pcap is running. Then stop it. Upload both files and note the IP addresses and hostnames of both machines.

It's highly likely this is not a bug in avahi or nss-mdns but a network issue of some kind. Hopefully this will get you going in the right direction.