Frequently, I've had issues with Windows machines accessing OS X Servers just set up with SMB sharing. It seems that the Windows client needs to allow a certain type of authentication to allow the machine to log into the OS X Server, and that setting isn't correct by default. The problem also happens for Linux servers as well, not just Mac OS X Server.

Note that by making these changes, you're making things that much less secure on the Windows side of things by allowing an older, less secure encryption method for authentication. While most of you won't care (because you're just looking for a solution for an in-house server), if you're working with a server which is publicly available (for some crazy reason), then get to know the facts before making these changes.

Here's directions on how to make that change in many of the various flavors of Windows: