Domain controller cannot browse network

I had a 2003 domain which was working fine until recently. I added an
Exchange 2003 server and then migrated to a second Exchange 2003 server.

After I had done this my domain controller lost it's ability to browse the
network - I started getting messages '\\Servername is not accessible. You
might not have permission to use this network resource. Contact the
administrator of the server to find out if you have access permissions. The
account is not authorized to log in from this station'

I have since been unable to open any mailboxes on my Exchange server - they
get the 'Unable to open your default folders. The Microsoft Exchange Server
computer is not available. Either there are network problems or the Microsoft
Exchange server computer is down for maintenance'
However I can open mailboxes using OWA with no problem.

As a test I added another domain controller which could then browse the
network fine so I moved all the DC roles to this new DC. In Exchange I then
changed the GC to the new DC and the recipient update services - made no
difference.

I don't get any error messages in the event logs to indicate any problems
and having run DCDiag, Netdiag and AdDiag they all report no problem.

After adding the second DC, workstations are unable to browse the Exchange
server and cannot resolve any entries in the address book - I get a message
to say 'Logon failure: the target account name is incorrect'

I am at a loss as to what the problem could be - or even if they are related.

DNS appears to be ok and all servers are on the latest service packs (SP1
for 2003 , SP2 for XP and SP1 for Exchange 2003). Windows firewall is
disabled for the purposes of testing and I have Mcafee AV software.

Any suggestions - other than to rebuild the domain!

Shutdown the first DC after removing File and print sharing and Client for
Microsoft Networks and it seems to have resolved the Exchange problem - after
restarting the services.

Then re-installed F+P and Client for MS Networks

From a client perspective, they can open mailboxes but when exploring 'my
computer' the 'My network places' doesn't show the 'Entire nework' option. I
have to then explore 'my network places' and then it appears and I can browse
the domain.

I also have a 2-way trust with another domain - I re-created it and it's
validated in both directions but people cannot open their mailboxes - it says
that the exchange server is not available - I'm therefore not entirely sure
my problems are solved!

Something is really up here - I thought I was half-way there but the problems
have come back.

On my XP box I now cannot open any mailboxes or resolve names in the address
book using Outlook. I also cannot browse the exchange server - I get logon
failure error messages.

I can't see why this is happening intermittantly - very annoying!