Martian

You say you used to be able to see it. Was that last week, last month, last year? Have their been any significant hardware or software changes between then and now?

I rarely deal with Macs and no little about them, but when I have issues getting a linux box and a windows box talking to each other, my first avenue of investigation is always network topology. Windows Networking is incredibly fragile that way, and doesn't like subnets or anything that could potentially get in the way.

Discovery occurs on the network via broadcasting (UDP, I believe) and a restrictive firewall can cause problems as well.

EDIT -- Bonjour? That's Apple's zeroconf implementation.

My apologies; I may have jumped ahead a bit here.

What is it precisely that you're trying to do? Are you sharing files between boxen, streaming media, etc?

Windows file sharing is typically accomplished via SMB; specifically, Microsoft's 'extended' implementation of SMB that's typically referred to as Windows Networking (formerly known as Network Neighbourhood). I don't know what the Mac client for SMB is, but in *nix Samba is the generally accepted means of accomplishing this. Given OS X's heritage, there's a strong chance that it's exactly what you'll need, too.

These sorts of things can be difficult to diagnose without physical access to the boxen in question, but I can try to advise further. Important things to know is whether the different boxen on the network can ping each other, as well as a general overview of the network topology.

__________________
I wake up in the morning more tired than before I slept
I get through cryin' and I'm sadder than before I wept
I get through thinkin' now, and the thoughts have left my head
I get through speakin' and I can't remember, not a word that I said

- Ben Harper, Show Me A Little Shame