A mi me paso eso mismo el jueves pasado, estaba instalando un programa y me instalo tambien el Contraviro, cuando termina la instalcion aparecio un mensaje del Avast diciendo que se habia encontrado un virus, le doy a eliminar y se me reinincia el ordenador, y me ocurrio lo mismo que dices, que no aparecen ni los iconos ni la barra de tareas, pero a mi me salia un mensaje diciendo que habia un error en "explorer.exe"
Me meti en el modo seguro con funciones de red y desinstale el Contraviro, el cual te pide registrarte en una web para que te den un codigo para poder desinstalarlo.

Le pase el Avast pero no podia eliminar algunos archivos infectados, y tras dos 2 dias sin avanzar nada, ya que no podia hacer nada, ni restaurar el sistema, ni instalar programas, pues cogi, guarde en un Pen todos los archivos importantes y formatee el ordenador e instale el Windows 7.
Pasale el antivirus y haber que ocurre.