Try hijackthis. Awesome wee program. I use it all the time to cleanup peoples IE installs. (I'm assuming it was IE that was hijacked)
Run it, do a scan, tick all the BHO entries the do the cleanup selected items.
|MG| Free Download - HijackThis 1.99.1
As for the LAN thing - that's a seperate issue. Albeit caused by the same spyware. Hijacked DNS can't stop you changing the default homepage. Although it could redirect any DNS lookups to different servers.