Um, a little late to the party, but the loss of Internet connection is the result of the FakeAV app setting up a proxy in your Internet browsers, pointing to itself on your own PC. Since it wasn't running, all that would have been needed is to remove the proxy setup in the browser.
However, the FakeAV installs a rootkit, which will eventually reinstall the fakeAV app. Unless your real AV is good at rootkits, it would have come back.
Combofix kills it, though. You still have to manually remove the fake proxy settings in your browser, but it's killed.
As for how it got there in the first place, its installer comes most often from a malformed web page or an ad, which may not even present itself on the screen. What it does do, however, is take anything you do and intercepts it, passing it to Windows as permission to install. That's why your real antivirus has no clue about it when it first appears. it goes to the OS as an app with full permissions to be installed.
Once installed, it intercepts anything you try to do and claims it's infected, you have to activate your scanner. Of course, there's the fraud. "Activating" does nothing but temporarily turn off the fake and let you have the computer back. Only costs you 50 bucks!
Its only weakness is that it takes a while to start once you log on to your desktop. You can use CTRL-ALT-DEL while the desktop is starting up and go ahead and start the Task Manager, Regedit, Internet Explorer, and a Windows Explorer window, none of which it will allow once it's running. It won't kill them once they're up, though, they work just fine. You can find the process in Task Manager and kill it, and you regain control of your PC, and since IE is open, you can go get Combofix and run it. Once Combofix has completed, which takes a while, your PC is back, as it was, with nothing missing except the rootkit which would re-install the thing.
