What I always do when my Mac can't see something on the network that I think it should be seeing is to use an app like IP Scanner (I'm sure there are others) to search the address space and tell me what's there.
If IP Scanner sees the device, but the Mac doesn't, then obviously I have to work on the Mac. But sometimes IP Scanner doesn't see the device at all, which is a different problem.
So I'd check that out first. I do realize that your Linux machine can see them, but I think you need to be as thorough as possible so you can declare that they're out there for sure as seen by your Mac.