... But.... (But always makes things more interesting.)
When they navigated to some directories on the share there was a noticeable pause before the contents were visible.
- The problem went away if they were added to the Admin's group.
- The more files or folders in the directory, the longer the delay.
- Network captures showed no issues with connectivity or name resolution.
And most interestingly, the problem did not exist on the Windows 2003 server in the same subnet as the new file server.
The problem was that ABE, Access Based Enumeration, was enabled on the new server but not the old one. ABE is this cool-but-noone-knew-about-it feature of Windows 2003 that would not let a client see a file or folder on a share unless they had access to it. The feature is awesome, but it means that the file server has to iterate through the permissions of every file and folder before returning the list of objects back to a client PC. For small folders, this was no issue. For this particular client's really-big-folders with painfully nested permissions it can cause a few seconds delay when browsing.
They aren't using the features of ABE, so clearing the checkbox fixed it.
Note: This issue was just a couple of seconds pause when browsing an open share. If you're experiencing a 15 or 30 second pause when initially connecting to a share then that's different. 15 or 30 second pauses are almost exclusively Name Resolution issues. Good Luck!