Are you sure it has to do with SP4 on the local machines? Have you tried looking at your print server (if you have one). It's kinda difficult to troubleshoot not knowing all of the details of your network. Just keep in mind the full path of your printing: Workstation to Print Server to Printer (if thats even the case in your network).