Do all these access a print server? I came across this on a Fultus tech doc. (you might have already seen it):
If you have a small network consisting of several (Linux) machines and have set up a print server for it, avoid configuring the printer for each and every client host by enabling the broadcast function of the daemon (see above). Thus, when you modify the configuration (for instance, to use the new standard paper size Letter), it is sufficient to do this once on the server side (also see 6). Although the configuration is saved locally on the server side, it is propagated to all clients in the network with the help of the CUPS tools and the IPP protocol.
It seems to apply to your situation, but without giving more information about your network, I don't know if many of us will be able to help, unless we've had the same problem.