Why is my OSX client having so much trouble connecting to our SMB server? I've already asked this question on ServerFault, but I'm beginning to think that this might be an issue more with my OSX client machine than our SMB server.

I'm using 10.9, but this problem happened when I was on 10.8 as well. When I first connect to our SMB share (hosted by some recent-ish windows server, not linux or osx server), the Finder seems to lock up for a good 30 seconds while it fetches the root folder of the share. Navigating the share is extremely slow at first as well - it takes about 30 seconds to open each folder. In the system log, I see this message repeated many times:

Apr  9 15:14:37 teds-mac-mini.teradici.local NetAuthSysAgent[2139]: smb_mount: mount failed to teradici.local/data, syserr = Permission denied
Apr  9 15:14:39 teds-mac-mini.teradici.local NetAuthSysAgent[2139]: NAHSelectionAcquireCredential The operation couldn’t be completed. (com.apple.NetworkAuthenticationHelper error -1765328228 - acquire_kerberos failed tmiddleton@LOCAL: -1765328228 - unable to reach any KDC in realm LOCAL, tried 0 KDCs)
Apr  9 15:15:11 --- last message repeated 5 times ---
Apr  9 15:15:11 teds-mac-mini.teradici.local NetAuthSysAgent[2139]: smb_mount: mount failed to teradici.local/data, syserr = Permission denied
Apr  9 15:15:13 teds-mac-mini.teradici.local NetAuthSysAgent[2139]: NAHSelectionAcquireCredential The operation couldn’t be completed. (com.apple.NetworkAuthenticationHelper error -1765328228 - acquire_kerberos failed tmiddleton@LOCAL: -1765328228 - unable to reach any KDC in realm LOCAL, tried 0 KDCs)
Apr  9 15:15:16 teds-mac-mini.teradici.local NetAuthSysAgent[2139]: smb_mount: mount failed to teradici.local/data, syserr = Permission denied


Eventually the delay in opening folders goes away and I can successfully navigate the SMB share. When the SMB share is responsive, no new messages like these show up in the system log, so I'm inferring that they're related to the problem I'm seeing.

I'm using a local account on my mac - I don't know whether its possible to log into a mac with ldap or active directory, but I'm not doing either of those. I do, however, have an active directory account here at work, and I can use that to access network resources at work (indeed, that's how I'm logging into the SMB share).

Any ideas what might be going wrong here? Is it an OSX/client issue? Could it be an issue with the SMB server? Active directory?
I'm having the exact same problem on my client.  Looking at a WireShark trace, there is always a 45 second delay in opening the connection the the file share (OSX Server 3.1.2).  Using SMB1 (CIFS) does the same thing and WireShark confirms SMB vs. SMB2.  Any other ideas out there?