Hmmm...this is separate from using SAMBA?
I tried setting up SAMBA by itself (on Debian) for Time Machine, but for it to work it seems to want Avahi running for mDNS; the problem is there is some weird bug or maybe user-related blooper where it collides with itself from time to time, leading to local DNS weirdness