Minha opinião é que algo se intalou no seu Ubuntu, automaticamente ou não. Não é vírus, e sim adware, está exibindo propagandas intrusiva para ganhar dinheiro. Não é problema de algo que se instalou no seu Windows, programas dele não rodam no pinguim. Não acho que será fácil remover, pois não é comum que algo assim aconteça. Se você tem o mínimo de experiência no Windows, deve saber o inferno que é remover esse tipo de coisa. No seu lugar formataria o computador e instalaria os programas um por um no LiveCD, algum deles fez isso, não sei qual, pode inclusive ter sido um que você usa a mais tempo e que 'virou' para o lado do mau. Não há garantia de que removendo isso ele deixará de estar no computador, pode, inclusive, estar lhe espionando.
Seu caso abre uma série de preocupações para mim, pois algo se instalou sem você deixar e talvez até sem ver. Será que finalmente teremos de sair da zona de conforto no Linux?
P.S.: tenho um pouco de experiência com Windows, logo, sou meio paranóico.