Authentication from Outlook to Windows Server 2008 LDAP AddressBook

We have a Windows Server 2008 R2 with Active Directory that was recently promoted to PDC when we decomissioned the old Windows Server 2003 PDC. On the old server users were connecting their Address book in Outlook to the server. They would point to the server name and use a specified Active Directory account to authenticate.

After we moved the active directory over to the newly promoted Server 2008, users cannot connect their Address book. All settings in the Outlook AddressBook settings are the same except the Server Name: has been changed to refelct the new server.

Users receive this message when they try to access the AddressBook: The '@' symbol replaces the server name.
********************************************************************************
Microsoft LDAP Directory

Failed to connect to '@@@@@@@' due to invalid authentication.
Ensure a valid user name and password has been entered on the Microsoft LDAP configuration page for the "@@@@@@@' account.
********************************************************************************

I tried changing the account to the Administrator account and it connected without any problems. I checked the event logs on the new server and found this error.

********************************************************************************
An account failed to log on.

Subject:
      Security ID:            SYSTEM
      Account Name:            SERVER$
      Account Domain:            DOMAIN
      Logon ID:            0x3e7

Logon Type:                  3

Account For Which Logon Failed:
      Security ID:            NULL SID
      Account Name:            TESTACCOUNT
      Account Domain:            DOMAIN

Failure Information:
      Failure Reason:            User not allowed to logon at this computer.
      Status:                  0xc000006e
      Sub Status:            0xc0000070

Process Information:
      Caller Process ID:      0x1e0
      Caller Process Name:      C:\Windows\System32\lsass.exe

Network Information:
      Workstation Name:      SERVER
      Source Network Address:      111.111.111.10
      Source Port:            2508

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

I tried adding the TESTACCOUNT to the Remote Desktop Users on the SERVER, but still receive the same authentication error and see the same event log.

I guess I am unsure if their is something additional I need to do somewhere else on this new server to allow users to access LDAP information. At this point I am totally at a loss on why this user account cannot access the AddressBook.

Any and all help would be appreciate.