Authentication issues on domain with multiple DC's/Member Servers

Until November 2007 I had one domain controller with a number of member servers running a mixture of Windows 2000 Server and 2003 Server. In November I added a 2nd Domain Controllers running Windows Server 2003 R2 at one of our interstate offices, connected via VPN. Since then I have had authentication issues with services on some member servers, where if an SQL Service is configured to run with DomainName\Administrator, when you restart service/server it has an authentication issue, re-enter the details and is fine until the next restart.
I also have some clients that when they change their password it accepts it, but then when open Outlook (Exchange 2003 Srvr) it doesn't recognise it, and I have to change it in AD to what there new one was.

I am guessing I have an issue with Global Catalog or somethign similar?? Any help to resolve this would be appreciated.
Cheers.