Soooooo, I’m still stumped.
Is there a firewall on the linux box? Can you turn it off for the purposes of experimentation?
If you have iTunes open, and start/stop the mt-daapd server, does it reappear?
What version of mt-daapd? And where did you get the package, or did you compile from source? And if so, what did you configure as a mdns backend?