There was an update recently for IE. Maybe the update changed the program, and the firewall no longer grants it access because it is a changed program. After you rolled it back, you got rid of the update so the firewall recognized it as a program that had permission.
Do they have a firewall? If not, then don't bother reading the part above.
See if they can get used to a different browser. IE might be easy for them to use, and sometimes people can be hard to change their ways, but they might be safer if they use Firefox or Opera.
It would be a good idea to get another browser anyway, because you might need one if you have to download IE 7 to reinstall it. Yes, you CAN download IE 7 with Firefox, I just tried it right now to be sure. I had to do the same thing years ago with IE 6. I restored my computer, and it had IE 5, and I couldn't get it to update, or upgrade to 6. So I had to put Firefox on a thumbdrive.