I posted this to link Brian referenced as well.
I was getting the same thing with network printers on a win2k sp3 pc connecting to a 5.5 update 2 server.
Here is what I did to fix things for me:
I created another network printer with the same IP address as the one that wasn't working. This printer worked. I still could not connect to my original printer. So, I created another network printer with the same IP address as well. This printer also worked. Then my original printer connection came back as well. So now I have 3 network printers defined with the same IP address. I deleted the 1st one, my original connection still worked, I deleted the 2nd one, and my orginal connection still worked. I went ahead and deleted my original one and re-created it with the same name, settings, etc. and it still works. I rebooted the server, and the printer still works.
I am not quite sure what the real issue is, but the above did fix it for me.
YMMV,
JB