I've seen this kind of error many times.
The first step I'd use to troubleshoot the problem would be to check for NDS synchronization. SET DSTRACE=ON and look for ALL PROCESSED=YES for all the replicas on that server. If your NDS is not sync'd then your NLSLSP will not function properly. You'll have to resolve the NDS sync issue before moving on.
After you've resolved any NDS sync issues, then unload NLSLSP from the offending server
and reload it. If the NLSLSP loads without errors, it narrows the problem down to communications with the Master replica for either the partition of the tree.
If the problem persists, then I'd recommend that you install the latest version of NLS of the offending server.
Another thing to lookfor is to see how the server looks for licenses. If it has to look to the root of the tree, and doesn't have a copy of the ROOT partition, then NLSLSP will not load until the server has sync'd with the master of the ROOT.
Hope it helps point youin the right direction.....
If this does continues