Flaky connection to a computer

We have a situation where we are having problems making a
connection to a user's PC. The machine has run without
incident for approximately 5 months. It has a shared
printer attached to it, and the symptoms are that several
times a day people can no longer print to it, nor can
they delete and re-open the connection to the printer.
When you go to the computer name under the network and
try to connect, you get the message "The network path was
not found" or "<computer name> is not accessible. You
might not have permission to use this network resource.
A device attached to the system is not functioning." It
depends on how you try to connect to see which message
you get.

The problem is not with the printer or the printer
driver. The printer has since been relocated and
reshared, and the driver uninstalled and reinstalled
several times.

Something that has helped is if we do an ipconfig/
release and /renew on the other machines trying to
connect. Sometimes this lets them back in for a while
and they can reconnect and print. However, the effects
are always temporary.

Any suggestions on this one are appreciated in advance.