Active Directory User Synchronization stopped working

We are using NAV 2009 Classic with Windows authentication. For some reason, new users added in Active Directory are not appearing in the list of Windows Users when adding a new NAV user. I have synchronized All Logins numerous times with no luck. Active Directory does function properly with SQL Server and I can manually add the user to the NAV database, but even with doing this, the user doesn’t show in the list of Windows Users to add in NAV. I’m at a loss. Any help would be most appreciated. Thanks!

Re-boot of main DC solved the problem.