Bummer.
Before you do anything too radical, we can test if multicast is getting through the router using iperf.
Install iperf using apt-get on two machines that can’t see each other.
Then on one machine, which will be on the listening end, run:
iperf -u -s -B 224.0.0.251 -i 1
On the other (sending) end, run:
iperf -u -c 224.0.0.251 -t 5
The sender will stop after 5 seconds, but you’ll need to to ctrl-C the listener.
(I’ve used the same multicast address as zeroconf but any 224.0.0.XXX address will do.)
For completeness, you can always try it both directions.
If nothing gets through, it’s very likely to be your router that’s the problem.