Once I came across the same thing, except it was with NT server, the win9x machine could not connect, so I tryed pinging the IP address of the server, and this got a responce. I then started to look at the machines configuration, I boiled it down to the Protocol installation being corrupt, so I uninstalled the Networking from the win9x machine. the reinstalled after rebooting and all worked okay.
Iain Brodie