I solved the problem.  The KB reads:

“The Novell Client will wait for the Windows network interfaces to become available, and will retry for a short period of time if "Tree or server not found" conditions are encountered during the eDirectory logon attempt. But if the eDirectory logon attempt ultimately fails for any reason (eDirectory tree can never be found, account password is incorrect, etc.), the Windows service will simply be allowed to start without an eDirectory login being available. There will be no future attempts or retries while the service is running, until the Windows service is shut down and then started up once again.”

I restarted the service and found that everything started working, so the KB is still accurate.  I wondered if the service was starting before the network was up.  Checked and saw that the service was set to Automatic startup.  Changing it to Automatic (Delayed Start) startup solved the problem.

Great that you already figured out a way forward on that.

Yes, we do expect that the service login configuration between SP4 and SP7 is still the same, and the same configuration would have been expected to succeed.  Indeed it sounds like the previous usage just happened to be for a service which didn't start until after the network was available to perform the login, but the service configuration and/or performance of the latest machine was allowing the attempt to occur even earlier.

what is the service?