Hola jariza, gracias por responder.

Nop, no habíamos instalado nada nuevo, y sip, eso que propones también lo hicimos, pasamos el Panda, el Trend Micro, el Ad-Aware y el Spy-Bot, pero nada.
Pero eso sí...lo hemos solucionado!!!
O al menos eso parece. Volvimos a desinstalar, pero esta vez desactivando el Restaurador de sistema de Windows, luego pasamos un par de veces el TuneUP después nos metimos en el registro (no sin antes hacer un Backup exportando Todo el registro) y nos cargamos todas las entradas referentes al programa en cuestión. Por último reinstalamos y Voilá...todo parece OK.

Gracias a los dos por vuestra ayuda.

Saludos.