Did you reboot after running the utility?
Did you run the utility in the computers' safe mode?
If so, (or if you now try it, and still no luck) try reinstalling the Avast program. Reboot as prompted, then disable the program from the tray icon, (stop On-access protection), there should be a confirmation prompt, click yes, then try uninstalling it again, in the usual way, from "add/remove programs".