When my husband's computer got infected with malware (a similar thing to what you had) - it would not let us reinstall Avast anti-virus or anything (didn't lock up the PC, though).
I found the site
http://www.majorgeek.com and their forum was EXTREMELY helpful in getting his system clean.