Right. In that case the DNS search zones aren't set up in the System Preferences>>Network>>Built-in Ethernet>>TCP/IP panel. You should enter your Windows domain's long name as a minimum.
Also, in your Utilities folder (Go menu in the Finder has a shortcut), you'll find a program named Directory Access. In there, select the SMB/CIFS option and click on the Configure button. In the workgroup box, type the short name of your Windows domain. Then in the WINS box, type the IP address of your WINS server.
You'll be able to get all of this information from the Windows PC by opening a command prompt and typing "IPCONFIG /ALL".
All this does is allow the Mac to resolve the name across the router. After that, you should be able to set up the printer using the Print and Fax method above, only the format for the address is "smb://printserver/<print queue name>".
I know it seems long winded, but once the networking side is done once, it will be much easier to set up additional queues in the future.
And unfortunately I'm going to have to butt out for a few hours now. It's bedtime here in Europe

. Good luck.