[Samba] Windows 2003 Intermittent problem

[Scott]

Hello, we have been running a linux machine on a Windows 2000 network for a 
couple of years with Samba 3.0.9/RedHat EL and have had no worries. The network 
staff recently upgraded two DCs to Windows 2003 (one was the PDC emulator) and 
there are several remaining Windows 2000 Domain Controllers. Now we are 
experiencing intermittent problems. Sometimes we are not able to see the Linux 
server at all, sometimes we see the Linux server but cannot access shares (we 
get the pop up window asking for name/password), sometimes it works perfectly. 
Sometimes logging off and back on will grant us access to the shares but not 
always. 

We have already tried disabling SMB Message Signing and enabling NTLM 
authentication on the DCs with no luck. 
Restarting the Linux services does not appear to affect things one way or the 
other. 
We are able to see users and groups in the Active Directory through wbinfo and 
getent.
We are able to connect to Windows shares from the Linux box.
We are able to get tickets with kinit.
We are able to use smbclient to retrieve files from Windows shares.
Apache is able to get user name information from the domain.
The Samba server is on the same network as the PDC, so there shouldn't be any 
delay over slow links.

Any help is greatly appreciated.

Thank you,
Scott