Sbryan,
This is just a shot in the dark but i can vaguely remember the details, we encountered a similar problem and using uninstall and office eraser to remove MS Office, and then after a fresh install all was well, Perhaps you could try this on one workstation perhaps to see.
The actual cause of this problem I can't remember but I think it had to do with the CD it was installed from.
Regards
Jack