I got one of these Google redirect viruses on my old computer. Instead of fixing the problem I got a new computer (which I needed anyway, unrelated to the virus), so nothing I tried worked before then. A temporary solution is to right-click new-tab any Google link you click, which will actually take you where you want to go. It's a pain in the ass, but if you've got the same virus then it's really the only inconvenience I had to deal with