This could be a ton of different things, trust me I've had to track them all down at one point or another. When the Web application you're trying to access was created, what type of authentication was specified, Kerberos or NTLM? If it was Kerberos, were all of the service principal names created? In addition, for Kerberos to work correctly your DNS Servers need to have the correct host and reverse lookup records created.
If service principal names have been created, have the service accounts used to host the Web applications been trusted for delegation in the Active Directory domain? What is the domain operations and forest operations level? If this it's 2000 or 2003 you will have to add the service accounts to different built in groups.
What server operating system are the domain controllers installed on? If it is 2008 R2 and service pack one is NOT installed, but the SharePoint servers are 2008 or earlier then there will be a problem with encryption between the SharePoint servers and the domain controllers. If this is the case make sure you've fully patched the domain controllers.
Make sure the domain is in good health by running dcdiag. Ensure that all of the tests come back without issues. If problems are discovered you will have to correct them before moving forward.