I have a Windows Server 2008 R2 new clean install , not a VM, that I have added to a Windows Server 2003 based domain using my account which has domain admin rights. The domain functional level is 2003. I performed a clean install of SQL Server 2008 R2 using my account which has domain admin rights. The installation completed without any errors. I logged into SSMS locally and attempted to add another domain account by clicking Search, Advanced and finding the user in the domain. When I return to the "Dialog - New" window and click OK I receive the following error:

Create failed for Login 'Domain\User'.  (Microsoft.SqlServer.Smo)

An exception occurred while executing a Transact-SQL statement or   batch.  (Microsoft.SqlServer.ConnectionInfo)

Windows NT user or group 'Domain\User' not found. Check the name again. (Microsoft SQL Server, Error: 15401)

I have verified that the firewall is off, tried adding a different domain user, tried using SA to add a user, installed the hotfix for KB 976494 and verified that the Local Security Policy for

Domain Member: Digitally encrypt or sign secure channel

Domain Member: Digitally encrypt secure channel

Domain Member: Digitally sign secure channel

are disabled none of which have made a difference. I can RDP to a Server 2003 server running SQL 2008 and add the same domain user without issue.

Also if I try to connect with SSMS to the sql server from another system on the domain using my account I get the following error:

Login failed. The login is from an untrusted domain and cannot be used with Windows authentication. (Microsoft SQL Server, Error: 18452)

and on the database server I see the following in the security event log:

An account failed to log on.

    Subject:
Security ID:        NULL SID
Account Name:       -
Account Domain:     -
Logon ID:       0x0

    Logon Type:         3

    Account For Which Logon Failed:
Security ID:        NULL SID
Account Name:       myUserName
Account Domain:     MYDOMAIN

    Failure Information:
Failure Reason:     An Error occured during Logon.
Status:         0xc000018d
Sub Status:     0x0

    Process Information:
Caller Process ID:  0x0
Caller Process Name:    -

    Network Information:
Workstation Name:   MYWKS
Source Network Address: -
Source Port:        -

    Detailed Authentication Information:
Logon Process:      NtLmSsp 
Authentication Package: NTLM
Transited Services: -
Package Name (NTLM only):   -
Key Length:     0

I am sure that the "NULL SID" has some significant meaning but have no idea at this point what the issue could be.