First off, what is the name of this fake AV running? It's important to know as some removal programs have been written that specifically target certain fake AV's.
If you can, d/l and run Norton Power Eraser.
http://security.symantec.com/nbrt/npe.asp?lcid=1033 Quote:
Because the Norton Power Eraser uses aggressive methods to detect these threats, there is a risk that it can select some legitimate programs for removal. You should use this tool very carefully, and only after you have exhausted other options.
You may want to try running a boot recovery disk which will initialize before the system files do. Here is a list of them with links to d/l:
FREE Bootable AntiVirus Rescue CDs Download List
Also, if you can, you can go here and do an online scan:
http://security.symantec.com/sscv6/WelcomePage.asp
Click on the "continue to security scan" button. The virus scan engine will d/l onto your system. Please note, you must be using IE to utilize this service.