Locked out of google, yahoo, many others

Hi, sorry if I'm going about this the wrong way, but I'm at my wits end here.

I can't access any search engine like google, yahoo, and also lots of other sites (eg. Piratebay, Filelist)... I can get to the first page of google, but if I try doing a search it just...loads. and loadsandloads forever. I'm not being redirected, there are no error messages.... the search result just won't load.

I actually found this site through msn.com - the only search engine I can use right now.

The problem occurs in both IE and Firefox.

 

I followed the instructions in the Malware removal guide. But just as I downloaded CCleaner, I decided to run MSconfig again and checked what stuff was being started by autostart. I found a file called nbtdtyh.dll. Renamed it "usedtobecallednbtdtyh.notdll". Then I restarted my computer. Computer now wouldn't start at all, during windows startup it threw up some weird blue screen of death with text that scrolled to quickly to read, then rebooted.
Eventually managed to find a a startup option that worked, and after shutting down from this mode (Safe mode with command prompt) the computer started fine. Got a warning that it couldn't find nbtdtyh.dll. Removed nbtdtyh.dll from the registry using hijackthis.

Firefox and IE now finds all the sites it couldn't access earlier. Google here I come!

 

Fixed it. Found a file called nbtdtyh.dll that I didn't recognize. Renamed it, rebooted, computer completely dead. Rebooted in Safe Mode with Command Prompt, rebooted again. Now everything works fine.

My guess is that nbtdtyh was the randomly named active installed bastard-part left behind from a malware component ad-aware caught and deleted earlier...

I've checked around, and a lot of people got hit with this same problem on the 13th, same as me...

 

Oh, and I removed nbtdtyh.dll from the registry using hijackthis, so no more annoying errormessage on startup.