hmm i worried maybe that virus also deleting some windows component that important for installing avast (part of visualbasic maybe , like .dll or .ocx files) so try to open command prompt and run as administrator first (if win vista or win 7 in start menu search for cmd and right click "run as administrator") and then type sfc /scannow
Good idea on the file checker.
Has your system crashed recently? Any blue screen with errors?
Since avast did disappear there may have been some corrupted or maybe missing files. This is very abnormal for this to happen. I'm thinking that even though Malwarebytes found nothing you should go ahead and download and run OTS
http://forum.avast.com/index.php?topic=53253.0. The instructions are also in this link. I have notified essexboy who is a malware removal expert. He will be the person who will give instructions on what to do after posting the OTS log file. On how to attach the log please see my attachment.
Was there also a log file to go along with that error message? setuperror.txt?
You didn't mention anything about a firewall. What firewall are you using?
Also, are you logged on to an administrator account while performing the install? I am searching the forum to see if I can find anything else that may help.
Doing my best here to get this solved. I know this is a lot of questions but this is not turning out to be a simple problem to repair.