Unable to Access Default Print Service Except as Admin

[JCGuarneri]

An issue cropped up recently using the default print service installed with Portal/Server. When any non-admin user tries to print from a print widget or web map, we get the error below.

I checked the sharing settings and it is properly shared with the whole organization. I also tried explicitly sharing the service with certain groups, and that did not resolve the issue either. Is there something I'm missing in the settings or configurations? This had been working properly before. I'm not sure when it stopped, but I suspect it was pretty recent.

We are using Enterprise 10.9.1 in a single machine deployment.