I had the same issues as described above using IE7 on XP Pro. Very annoying but I have just this minute resolved the problem. I'd been playing with the registry up until now, but that was a waste of time as it never worked properly.

Run Hijackthis. It will give the following entries (perhaps more, perhaps less):

Code:
[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Internet Settings]
"AutoConfigURL"="YOURAUTOPROXY"
"ProxyServer"="YOURSPECIFIEDPROXY:PORT"
Go and find them in the registry and make a backup of the keys in case it doesn't work (although after 2 weeks of messing it did for me). The above is a copy from my backup .reg file. Tick the boxes in Hijackthis referring to the above entries and Fix them. They're deleted and you can change the settings in LAN settings once more!

Still don't know what the reason was for the inability to alter the settings though...