One of the first things I usually do (when it applies) is install the Windows Services for UNIX in the machine with the printer attached. It has fixed most of my problems. In fact OS X usually "forgets" or is unable to correctly identify via SMB with the remote printer/computer, even when you have either guest enabled or a specific user saved in your keychain.
Other than that, try manually browsing to see if you have access to the printer in the first place. If you can manually reach it, then you have a discoverability problem (usually fixed by the above steps) or the steps pointed in other answers.
For what is worth, installing those services on XP machines is very simple and it's included with the XP CD.
You don't really mention where is the printer connected (Windows Version) so I can only guess. If your printer is attached to Windows 7, I'd take a look at the other answers before going crazy.