Printer problems

I am trying to add a printer to some pc's in my network. The printer works locally on the person's machine and I have shared it and listed it in the directory. When I go to another machine to add the printer it does show up in the directory but I get an error msg stating:

Windows cannot connect to the printer. Either the printer name was typed incorrectly, or the specified printer has lost its connection with the server.

He is able to access all network files and folders so I know the machine is still network connected. I have also tried re-installing the printer. Anyone have any ideas.