...to get your NetBIOS naming working.

Those Win95 boxen mean that that's the way name resolution is going to work.

Things to check : all boxes have NetBIOS bound to the same protocol (I suspect that as you've got a Linux box in the mix that this will be TCP/IP) and they're all in the same workgroup/domain.