In this case we had a Windows XP with SP2 machine in an office environment. On August 9th, 2008, we did an automatic update from Microsoft for the XP components which included all security updates and the now mandatory by Microsoft: Windows Genuine Advantage.

After performing the update and rebooting the computer, printing no longer worked. Reinstalling the printers did not solve the problem. We double-checked the firewalls and virus scanning software and it was fine.

Using Accessories | System Restore we were able to restore the computer to the pre-update state, and printing immediately worked again.