Users can log into PCs using Active Directory credentials but not Macs

Our environment uses Active Directory to allow users to log in to both PCs and Macs. Though we are mainly a Windows environment, we have several Macs and are getting more and more. We are now having users who will randomly be able to log into PCs but not Macs. Does anyone know how to fix this, or what may cause this issue? We have tried resetting user passwords in Active Directory, and checked security permissions but nothing seems to work. The last time this happened, we worked on it for a week or so and though nothing fixed it right out, it suddenly started working again one day.

We bind to Active Directoy, and then set the preferred domain in Directory Utility to our domain. Could it be that we don't have the boxed checked to allow log in from any Domain in the forest? It has worked in the past without this option checked though. Any help I could get would be greatly appreciated. Thanks!