I experienced an issue on a Windows 2003 server where it could not access certain network shares even though permissions and network connectivity were configured correctly.

While trying to access some network shares I got the following message: