I bet you this is the new Antivirus 2011 software. I have seen four different flavors of it this year alone.
http://download.cnet.com/RKill/3000-...-11464676.html
This link takes you to a download page for a program called RKILL.EXE
This program is the only thing that will stop this type of application from running. However, you have to do it in Safe Mode with Networking Windows for it to work. In normal mode, the application is just blocked with the same message as OP referenced.
Once you do that, download and install Malware Bytes. (it was recommended by the author of the rkill app. I imagine that any malware scanner could catch it.)
Running a scan, by itself, in normal mode or Safe Mode will not get rid of it. Safe Mode scan without RKILL will not pick up anything.