Two more things to check.

1. Make sure that the printer name and the printer share name are exactly the same on the print server. It will save you a lot of pain.

2. Check the event logs on the client for errors occurring around the time of the failures.