Just on the off chance... are you using either WinNT or Win2000, or maybe have multiple user profile set in Win98?
It sounds like it's a permissions problem when IE is trying to store the setting in the registry (unlikely with Win9x but it's still possible to have the registry hosed).
I'll try to hunt down the relevant key in question, but an idea of operating system version would start me in the right direction...