My PC is apparently hijacked with some sort of malware that is causing random porn sites to pop up (even if IE isn't running) at random. This malware is prohibiting me from running hijackthis, cmd, msconfig, taskmgr, process explorer, killbox, malware bytes, etc. Every time I try to run one of these I get a message telling me that these programs are infected and I need to register my (fake) antivirus software.

Any ideas for a starting point?

If you have malwarebytes already then rename it to something like fishy.exe, you may also be able to do the same for hijackthis.exe Rename it foolyou.exe. See if that helps.

No luck. It kills anything I try to run.

It appears to be some sort of fake antivirus. When I go to the properties tab on one of the windows for the fake av, it leads me to a "tujlsysguard.exe" file.

http://www.sophos.com/blogs/sophoslabs/v/post/7618

The link above is exactly what I have going on (but no help in fixing)

Update:

I think I have removed it. It was Antivirus Live. I was able to trace the fake alerts back to the source .exe file. I wasn't able to delete it; however, I was able to rename the extension. So I renamed it and restarted the machine. Upon restart, the malware couldn't load the .exe, so I was then able to delete it and run Malwarebytes.

I suppose this thread can be closed.

Excellent, glad renameing helped you out. Good luck.