We are experiencing some intermittent problems with Authentication on a Windows 2008 Standard Server. The Active Directory Store is on a separate Windows 2003 Server. Sometimes, when we try to access the server via a file Share or via an RDP Session, we will get authentication failures, but after a number of re-tries it will go through as if there never was a problem. There doesnt appear to be any activity in the Event Logs either showing errors happening at this time. Any advice on how we should go about investigating this would be helpful.
I would check event logs, especially the security logs, on both the 08 server and all DCs. You didn't specify which logs you checked.
If none of the logs still show nothing, I would also run a packet sniffer like WireShark and monitor the traffic on the 08 server. I would compare what a successful authentication looks like to an unsuccessful authentication. Maybe this will show you something not otherwise seen.
I would also check firewall logs, too.