Automatic logon to an AppleShare server is done through two pieces of
software: The AppleShare file itself (the RDEV that appears in the Chooser
and is also an INIT) and the AppleShare Prep file, which stores the
auto-logon information (volume name, password, and so on).
If the machines fail to log on (but AppleShare is active) you can manually
mount the volumes without rebooting--then the most likely problem is that
the RDEV can't find the AppleShare Prep file during startup. This could be
due to either corrupt System software or a corrupt directory structure.
Because you've already rebuilt the System, it's probably the latter.
Run Disk First Aid against the hard drive. This does minor repairs on the
directory. You may also want to rebuild the Desktop. A definite cure
would be to back up and reformat the hard drives, but you will probably be
able to solve your problem without resorting to this.