A pesar de lo síntomas que comentas, no te olvides que es un simple virus, algo que viene ligado a Windows y de los que los linuxeros nos olvidamos por completo
Como dices que tienes Ubuntu en otra partición, te ofreceré dos posibles soluciones:
a) Desde Windows, arrancaremos en "Modo a prueba de fallos con funciones de red". Esto se hace pulsando F8 cuando va a arrancar windows.
Ahora es el momento de pasa antivirus, antimalware. Dices que te has bajado una versión "portable", que funciona desde un USB. Dependiendo de donde te lo hayas bajado puede ser que también vaya acompañado de "amigos indeseables". Te recomiendo que pruebes AVG Free (descárgalo de aquí:
http://free.grisoft.com/ww.download?prd=afe).
Se que existen "mejores" antivirus pero este es gratuito y si no dispones de una licencia, nos podrá sacar del apaño. Si cuentas con la ayuda de NOD32, Kaspersky o cualquiera en general, ejecuta un análisis y comprueba que te borra todo.
Yo también aprovecharía para pasar Adware de Lavasoft, un antimalware para aprovechar y desinfectarnos por completo.
Una vez hecho todo esto, solo nos queda reiniciar y disfrutar de nuestro pc limpio.
b) Desde Linux podemos utilizar el antivirus AVG Free. En vez de descargar el paquete para windows, utilizaremos el paquete de linux. Una vez instalado, solo queda analizar el PC. Ojo, ten cuidado porque analizará "todo" el PC, es decir, la partición raíz "/" y los subdirectorios, si quieres ahorrar un poco de tiempo analiza solo la partición de windows "/media/windows" (o algo parecido)
PD: Añado una guia de instalación de AVG en ubuntu:
http://ubuntuforums.org/showthread.php?t=136064