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