HELP. Malware/Rootkits keeping me from running any security software

All,
I've run into one tough bit of Malware. It began when Avast (I have the free version) popped up saying there was a security issue. Once it did pop up it disabled Avast, both the resident piece and the executable file. After that, the waring came up that the computer was infected and I needed to click yes to fix it. This was obviously the "fake" AV at work. I then tried to run Malwarebytes (MBAM) and it began to run then disappeared. It cause the exe file to become unusable (saying it couldn't be found or that I don't have the security rights) I tried to rename the MBAM exe file as a random name and as winlogin. Neither worked. I also tried pulling the MBAM directory from another machine, same problem.

After this I tried running every other AV - Anti-malware program I could think of, and each of them did the same (you name it I tried it). I tried to run Housecall (thinking an online program might work) Housecall began to run, then stopped. It then caused my internet explorer to get the same "locked out" status. I still have google chrome, but that's because I didn't try and download or run anything from there.

I then gave HiJack a go, so I could post a log file here in the forums. It ate that as well. It began to run, stopped, now the program gives an error when I try to run the exe file again. I have looked at all of the load and run processes in the registry (only one looked strange, and I deleted it) the processes that are running are all OK, but there are a few svchost entries that I'm sure contains my issue. I tried running process explorer, to see if I could get any deeper into what is running. It didn't even start, and locked the exe file.

I have done all of this starting in normal XP, and all of it also in safe mode. No luck at all. I tackled a bunch of these on different machines, including the one that just won't let you run exe files at all. This is a first for me. Any help at all would be greatly appreciated.

 

Hello Dr, thanks for you response. Here are the logs that I could provide. Malwarebytes wont run no matter if I run RKill or not, this malware has it (and other common AV/Malware programs) pegged. As a side note, I did run TDSSKiller as requested by the folks at malwarebytes. I deleted the hidden service it found, but it doesn't seem to go away after reboot. As he said, this is a "BAD guy". Thanks for you help.

 

OK, that makes sense. I just though there might be differing approaches (and there seemed to be) I used TDSSKiller and tried to delete the locked nasty service per LDTate's instructions and it just doesn't go away. I'll work with LDTate to see this through. Sorry for causing any duplication of effort, I do appreciate the help.