I had this same problem at work. I tracked it down to McAfee Virus Scan. Uninstall it, history works fine. Reinstall it, history doesn't work anymore.
At that time, I never found anything on McAfee's support site about the problem.
There maybe something there now, but I haven't looked. Switched everything over to Norton Anti-Virus.
