Google Redirect Virus

So on Thursday, July 19th, my computer gave me a few random billion messages claiming my hard drive crashed. Immediately, I restarted into safe mode and did a system restore to June.

Everything seemed OK, then I noticed when I googled things, if I clicked a link, I would get sent to a random website. My internet runs sluggish. I can't put my computer to sleep. It's generally screwed up.

My dad and I have been trying to figure out A) What's going on and B) how to fix it for over a week now. We've tried a bunch of things suggested on the internet, but we can't seem to get rid of this bug.

Is anyone able to help me?

What browser are you using?

It's unlikely, but it HAS happened to me in the past. Whereby, I've had a virus which has hidden itself as an extension of Google Chrome, meaning it was very easy to dispose of. A bit of a pain to completely uninstall but at least disabling it wasn't a problem.

Firefox 8.0 I believe. If I open IE, I get a virus warning about it trying to install random .dll's. Opera has the same problem as Firefox.

Sounds like lame malware. Malwarebytes should be able to get rid of it. Do a full scan in safe mode.

What kind of Virus scanner do you have? I'd suggest running a full system scan with it and do the same with Malwarebytes. If neither of them find anything you'd better retrieve all photos, videos and I-tunes songs from your drive and format it thus overwriting everything, only as a last resort. Unless you have a drive image from before the ♥♥♥♥ hit the fan. But first I'd run a full Virus scan and try Aniday's suggestion.

I'm trying Malwarebyte's right now in Safe Mode, although I have tried it in normal mode previously. I've also tried two TDSSkiller files, one from Kaspersky and another from Symentic or whatever it's called and neither will even load despite renaming them. I've seen a bunch of videos and read a bunch of websites where they claim to know where to find the actual files and delete them but none of what I've done looks like that.

I did do a backup of my hard drive the day that I got this virus, so should I run a virus scan on that external hard drive? Also, there is a tool that claims it can remove the virus for $30, should I even consider that?