When you restart the computer, does the malware boot up right away? If not, restart your computer, and before the malware boots up, open the task manager quickly, then terminate the program when it appears, so that you can open the programs you need to restore your computer. Then open up the control panel and click system, and do a system restore to a previous malware free state. If you don't have a good restore point, then at least you can download the programs needed without the malware shutting everything down. Hopefully this helps you.
Edit: Postjack, you don't need to go through the hassle of reinstalling your entire computer. A rogue virus is not a huge deal. If you cannot find a good system restore point, then at least open task manager quickly before the virus boots up and after you terminate it you can open up a browser to use software like this: http://www.malwarebytes.org/ to scan and remove the rogue virus from your computer.