1. Ran virus/trojan/spyware checks (it doesn't appear to be the product of a trojan as it remains on gateway.com)
2. Disabled/removed all anti-virus, anti-spyware and firewall programs as well as toolbars.
3. Disabled everything but the most crucial startup items
4. Relaxed security for Active X components
5. Removed and reinstalled IE Windows component
Then, I tried a few registry changes, but to no avail.
I then downloaded StartPage Guard. I tried to change the home page with that and I got the following error - RegSetValueEX failed with: 5.