Sounds like your logon script is not replicating between your two Domain Controllers... So your clients are only running the script when the DC that has the script is the one doing the authentiction.
On both of your domain controllers make sure the script is present. Script should be located in C:\Winnt\system32\repl\import\Scripts You should see your LogonScript.bat file on both servers. If not copy it from one to the other in the location above. NT file replication was always a PITA.
Also make sure the Scipts folder is being shared. A quick way to do this is to UNC to the server and look for a share called NETLOGON.
Eg. \\PDC01 Do you see a NETLOGON Share? if Yes, Open it. Do you see your logon script there? if Yes, server is ok. If no NETLOGON Share, that's the issue - the scripts directory is not shared as NETLOGON. If yes to the share, but no to the script being there - just copy script into the NETLOGON Share.
Also Check:
In UserManager select a user account that is not working. On the profile tab of the user properties make sure the name of the logon script is present.