After a *lot* to-fro testing (and a lot patience and help from Maximilian!), we've finally narrowed down the problem, and it is not a simple resolution issue.
It seems that the Kyocera printer is having issues when the data filter chain looks like:
Which is how CUPS currently calls Ghostscript with ps2write - so we ASCII85Encode image data, which is part of the page data stream. The page data stream is then LZWEncoded, and then that compressed page stream data is also ASCII85Encoded.
So we get that by using the following command line options for Ghostscript:
-dNoT3CCITT -dEncodeMonoImages=false -dEncodeColorImages=false
Which we settled on to work around filter problems with the Brother printers.
To get this Kyocera printer to print in a reasonable time, I used these options:
-dNoT3CCITT -dCompressPages=false -dCompressFonts=false
So we're compressing image data, but *not* the page streams.
I have a *feeling* we tried something like the above with the Brother printers, and it didn't work, but my memory is vague - we tried *so* many things! We might have to ask one or two of the Brother users to test for us again.