I think I've got a similar setup to yours, and I can print from my Linux box from the command line or KDE.
Here's how I did it:
I've got a original Epson Stylus Color on my WinXP Pro box, connected to the parallel port. I wanted to use this printer for output from my Linux box, running Debian Unstable. For printing purposes I have CUPS installed as my printing subsystem. Also, I used KDE's print management tool to set up the Linux side.
To set up the Windows side of this:
Right click My Network Places and click on Properties. Right click on Local Area Connection and click on Properties.
I have the following three drivers installed:
Client for Microsoft Networks
File and Printer Sharing for Microsoft Networks
Internet Protocol (TCP/IP)
If you don't have the File and Printer sharing installed, click the Install button and then click Service, and then click on File and Printer Sharing and then OK to add it to the list.
You then need to know the identification for this machine, so right click My Computer and click Properties. Click on the Computer Name tab and note the "Full Computer Name" and "Workgroup" entries.
Now open the Printers and Faxes folder (in the Start menu or by going through the Control Panel) and right click on the printer. Select "Sharing..." from the menu. On the Sharing tab select the "Share this printer" radio button, and then type in the share name.
Now for the Linux side:
I did this with KDE's printing management dialogs. Log into KDE as root. Open up the Control Center and then click on Peripherals and then Printers.
Click on the ADD icon and choose Add Printer/Class... and then click Next.
On the Backend Selection screen choose SMB shared printer (Windows) and click next. If you have the guest account enabled on the Windows box, click on the "guest account" checkbox, otherwise fill in the login name and password on this screen and click Next.
The next dialog is SMB Printer Settings. I have never gotten the "Scan" button to show me anything other than the workgroup name, so manually fill in the Workgroup and Server boxes using the info you recorded about the Windows box, and then put the share name for the printer in the Printer box, and click next.
Under "Printer Model Selection" choose your manufacturer and model number, and check off the "Postscript printer" button if that applies, and click Next.
On the next screen you may be able to choose between several drivers. Choose one for now, you can experiment later... and click Next.
This gets you to the Printer Test dialog. Run the test, change the driver settings, etc. until you like it.
The next dialog is Banner options, I don't print banners (only one user on this printer...)
The next dialog is Printer Quota settings -- I don't use those.
The next dialog is User Access Settings -- I don't use those.
The next dialog is General Information -- give this instance a name, fill in the location if you want, and change the description.
The last dialog just displays all your choices, and gives you the Finish button.
That's what worked for me!