Today, I dealt with another one of those fakealert viruses. This one was called windows restore. I had to take a couple minor extra steps. I booted to safe mode with networking. I found that the virus had removed the DNS servers (which had been statically set on this computer). I added those back and was then able to download malwarebytes. One thing that was super weird was that it had hidden all files and folders. I ran start -> run -> iexplore to start IE, but I also unhid all files.
After running malwarebytes and removing the virus, I found that all files were still hidden. I ran this from a DOS prompt to remedy that:
attrib *.* -s -h /s /d
And things were back to normal.
Of course I ran these instructions to clean the virus: