Well the problems you appear to be having will more than likely trace back to some
sort of setup, or configuration issue with Active Directory otherwise most of us would be
having a similar issue. Please use the information below to help you locate tools and articles
to help assist you in tracking down possible network issues.

If there is reliability issues with the network then the diagnostics should hopefully show that too
unless it is very sporadic which doesn't seem to be the case since you report that users have the issue
often.
 
A possible quick check that might reveal something is to check the Event logs on the client for issues with logon and policies
and hopefully that might show something obvious. If not then you need to start doing some basic network and AD
diagnostics to see where the issue resides.
 
See the bottom of the post for Tool Downloads that may be required for dianostics work.
 
Domain and Forest Trust Tools and Settings
http://technet2.microsoft.com/WindowsSer...3.mspx?mfr=true
 
    Some main Network diagnostic tools
  • Dcdiag.exe: Domain Controller Diagnostic Tool
  • Netdiag.exe: Network Connectivity Tester
  • Dnsdiag.exe: SMTP DNS Diagnostic Tool

 
Network Services Management Support Tools
http://technet2.microsoft.com/WindowsSer...3.mspx?mfr=true
 
 
Other possible areas to check out
 
Replication Does Not Work After Upgrading to Windows 2000
http://support.microsoft.com/kb/249261/
 
How To Diagnose and Test TCP/IP or NetBIOS Network Connections in Windows Server 2003
http://support.microsoft.com/kb/323388
 
Group Policy Home Page
http://www.microsoft.com/windowsserver2003/technologies/management/grouppolicy/default.mspx
 
Group Policy Troubleshooting
Updated: March 02, 2005
http://technet2.microsoft.com/WindowsSer...3.mspx?mfr=true
 
Troubleshooting Group Policy application problems (2000)
http://support.microsoft.com/default.aspx?scid=250842
 
Troubleshooting Group Policy in Microsoft® Windows® Server (document download)
http://www.microsoft.com/downloads/detai...;displaylang=en
 
Active Directory Operations Overview
http://www.microsoft.com/technet/prodtec...de/default.mspx
 
Active Directory Operations Overview - Troubleshooting Active Directory—Related DNS Problems
http://www.microsoft.com/technet/prodtec...t1/adogd10.mspx
 
Active Directory Operations Guide
Appendix A - Tasks Reference
This appendix lists all tasks, and pointers to their associated procedures, in alphabetical order.
You can build tear sheets for your operations staff by cutting and pasting procedures into a separate document.
These procedures can be part of an operations task assigned to an operator, or part of a task to troubleshoot an Active Directory component.
http://www.microsoft.com/technet/prodtec...2/adogdapa.mspx
  
Active Directory Operations Guide
Appendix B - Procedures Reference
This appendix lists all procedures in alphabetical order.
You can build tear sheets for your operations staff by cutting and pasting the task and its procedures into a separate document.
http://www.microsoft.com/technet/prodtec...2/adogdapb.mspx
 
NBLookup is a command line diagnostic tool that uses the User Datagram Protocol (UDP) to send
NetBIOS name queries to Microsoft Windows Internet Naming Service (WINS) servers
http://support.microsoft.com/kb/830578/
 
 
 
Windows 2003 Tool DOWNLOADS
 
Windows Server 2003 Resource Kit Tools 12MB
(DNSDIAG, REGINI, ROBOCOPY [XP010], SHOWACLS, etc...)
http://www.microsoft.com/downloads/detai...;displaylang=en
 
Windows Server 2003 Resource Kit Tool Updates
http://www.microsoft.com/windowsserver2003/techinfo/reskit/tools/default.mspx
 
Windows Server 2003 Service Pack 1 32-bit Support Tools 5.3MB
(DCDIAG, NETDIAG, NETDOM, NLTEST, XCACLS, etc...)
http://www.microsoft.com/downloads/detai...;displaylang=en
 
Windows Server 2003 Service Pack 1 Administration Tools Pack 4/28/2005
http://www.microsoft.com/downloads/detai...;displaylang=en
 
Sonar.exe: File Replication Service (FRS) Status Viewer
http://www.microsoft.com/downloads/detai...;DisplayLang=en
 
Microsoft ® Windows Server ™ 2003 Performance Advisor
http://www.microsoft.com/downloads/detai...;displaylang=en
 
Group Policy Inventory (GPInventory.exe)
http://www.microsoft.com/downloads/detai...;displaylang=en
 
Group Policy Management Console with Service Pack 1
http://www.microsoft.com/downloads/detai...;DisplayLang=en