Are you sure that all the user accounts are gone? I've run into several fake-AV infections lately that set the "hidden" and "system" attributes on nearly every file on the disk, then unchecked the "Show Hidden Files" option (so that hidden files really are hidden) and locked down the setting in the registry so it couldn't be checked. No user accounts or files were actually harmed, but they looked like they'd been erased.
The very first thing I would do: stop trying to boot into the infected copy of Windows! You need a boot CD, preferably one that was created specifically for cleaning up infections; the Dr. Web LiveCD (a Linux disk with a virus scanner and Midnight Commander on the desktop) is one of my favorites.
Once the actual infection is gone, you need to deal with the damage it's left behind; if I'm right (no guarantees, sadly) in your case, that will mostly mean un-setting the "hidden" attribute on all files, and the "system" attribute on the files where it doesn't belong (that's a question in its own right); probably restoring the file association for .EXE files (many of the FakeAV infections I've seen recently tell Windows to run the FakeAV first whenever you click on an EXE file; once the infection is gone, Windows no longer knows what to do with EXEs); removing and re-installing your (real) antivirus; and doing a full scan once everything looks normal.
To keep it from happening again: keep everything up to date! I recommend Secunia PSI to help you with that.