Well that sounds like a very sucky set of issues to deal with. Of course, you know you can't possibly be having these different issues on individual computers if they are all identical!
Hopefully you figure something out with this. Longer term, I think people are starting to have more and more issues with the Gates PC security software (and the Gates Security Tool on non="Gates" pc's), because it's now been over 4 years since that software has been updated. It was never even updated for SP2 - and as time goes on, updates and new software - especially things like AV are either poking more holes in the security or else running into these kind of conflicts.
It is probably worth thinking about moving to the MS Shared Computer Toolkit in the future. The next version of this should be out in a month or so (under a new name), and contains many improvements over version 1. Especially if you can't fully resolve these issues, it may be the way to go.
Dale