AntiSpywareMaster - No longer able to connect to web pages [IE]

One of my computers at home seem to have gotten infected by something, I took a look at this this morning and it had a program called "AntiSpywareMaster" installed and running (which is odd because the computer has both AVG and Lavasoft running - but anyways - this was causing AVG to "find a threat" every 30 seconds. I proceeded to uninstall the application and delete it from C:\Program Files manually, did some scans and everything seemed fine - but then I noticed one major issue - I cannot connect to the internet (Internet Explorer)...

Oddly enough - from that PC I can connect to my router (perfectly fine), my network is perfectly fine (copy files back/worth, etc...) but I can't connect to ANY web pages at all - IE gets the "page cannot be displayed" almost immediatly - but I know the internet works (posting this online right now).

I've tried a few things - thinking it might work...

I've already tried the following:
- HijackThis didn't see anything abnormal in the scan
- Ran VundoFix
- Ran ComboFix
- Ran CureIt
- Ran SmitFraud
- Full System AVG scan
- Full (deep) Lavasoft scan
- Deleted all files called AntiSpy*.* from C:\ Drive
- Deleted all AntiSpy* from registry
- Ran Internet Options -> Connection (LAN)
- Cleared TEMP folder, Internet Temp folder, History
- Windows XP sfc /scannow
(hell only thing left is to try a re-install before a re-format)

And yet - I am still utterly able to connect to the internet... Everything else seems to work perfectly fine, as if something got changed to block me from the internet itself (maybe in IE? Windows? etc...)
Anyone have any clues? At this point any help would be greatly appreciated.

The computer is running Windows XP Pro SP2... (incase that helps at all)...
Thanks,