Maybe you should have tried to do a system restore when the problem occured at first. If that function in Photoshop is really important, then maybe you can consider formating your hard drive, if you cannot find the source of the problem. I have never heard of this problem before, so I don't think I can help you much. If you run a legal version of Photoshop, then try calling the support.
Also, do you get this error message only when saving for the web?