It sounds as though they aren't finding the tree at first and are resolving NDS authentication another way.
What version of CSA and NetWare? Are you pure IP or a mix of IP and IPX? Do you have a scope set up and do you allow SLP discovery?
We are running NetWare 5.1 and 6.5. We have CSA 4.0.2 and 4.0.3 running on almost 1200 hosts and are running the 4.83SP1 client.
I remember a problem we had after installing the 4.0.2 client where things would not sink in until after a second reboot but I don't recall logins to be a problem.