Very weird network printer problem

One of our Optra T614 network color printers is causing a serious headache. We are running Win NT 4.0 servers and workstations. Some of the users can print to it while others get failed errors. All the users are on the same subnet on the same Cisco Switch. I can ping the printer from the users workstations who cannot print to it. What are the trouble shooting steps to fix this. We’ve taken a number of steps but none have solved it yet. Maybe you’ll have the right one 🙂

Thanks