Mein Problem hat sich gelöst.
Mein Admin-Vorgänger hatte Aufgrund einer Sicherheitslücke eine Policy erstellt, die den Spooler-Dienst deaktiviert.
Das ist aber irgendwie auf dem Printserver nie zum Tragen gekommen. Erst jetzt, als ich letzte Woche die Juni-Updates installiert hatte, wirkte die Richtlinie plötzlich.
Hab die Richtlinie jetzt deaktiviert und alle können wieder drucken.