Did you stop the Avast service before trying to uninstall it?I not, Ccleaner might have gone through the process, but given a false indication that it had completed the task.
You might be stuck in the middle now so do all of this:
Right click the icon, and click "Stop on Access protection." , Click Yes to the question which pops up.
Now type msconfig in the RUN, and open the "startup" tab
Untick any entries you may see which have Avast in them.
Reboot you computer, the icon will be gone. and now enter the Control Panel - Programs - uninstall a program.
If Avast is still there, Uninstall it.
If it is not showing, then it is mission accomplished.
Many programs have a problem removing superfluous entries from Vista so:
You can now enter the Windows Explorer and Program files. If Avast is still showing, delete the lot.
Defragmentation will not remove anything so you can disregard that, but now, if you run Ccleaner, it may find a few odd Avast entries in the registry, which it will take care of.