Vista/ Ubuntu printer sharing

OK, I've been having all sorts of fun trying to get my Vista Home Premium PC to use a printer over a network (All wired, D-Link DSL 2640B router) connected to another PC running Ubuntu 8.04. Until a few weeks ago, I had it working perfectly, but all of a sudden, Windows with its usual knack for these kinds of things decided that the printer was permanently offline. Reinstalling the printer drivers cured this, but only while the PC remained on; following a reboot it's gone again. Now even this seems to have stopped working, and violence towards my PC is becoming increasingly imminent.
For some reason, Windows simply refuses to believe that there is a printer at the IP address of the PC it is connected to, whether I let it scan for it or input the IP manually directly from CUPS. I am able to access the printer's CUPS page in Firefox and make it print a test page, so there is clearly some major problem at my end. If anyone could give me a simple, step by step guide to getting it to work from scratch, then I would be extremely grateful.
Powder