I've found a similar problem on my OS X set up at work, except that only one machine is visible under AFP file servers ( a b/w G3 350 running MacOS 9). The machine I'm really interested in connecting to is an old PowerTower Pro running SUSE Linux for PowerPC, with netatalk (ie AppleTalk for Linux). The whole network is clearly visible and works well under MacOS 9.
The only way I was able to connect to the Linux box was by entering its IP address in the Connect to Server dialog. This mounted the server - but none of the directories or files were visible to the Finder.
It gets interesting now. I opened a terminal window, and was able to navigate to the server and see most (but not all) of the 'invisible' files. Very strange.
My guess is that the problem is related to the way the OS X Finder hides UNIX-ish files.
My machine at work is as follows:
G4 450 with 384MB RAM, and a 20GB hard drive divided into two partitions (OS 9 and OS X respectively). Also two video cards - the original, plus another ATI card that works beautifully with my second monitor under OS X.