Eu tenho quase o mesmo problema no meu laptop MaxData de alguns anos (nVidia GeForce Go 7400). Listras verticais, principalmente vermelhas, visíveis especialmente na tela do modo BIOS / texto, menos em resoluções mais altas (1024x768). Há sempre cerca de 5 faixas cada 8 pixels de distância, em seguida, uma lacuna, em seguida, novamente listras e assim por diante. Além disso, quando no modo de texto, cerca de 1/3 de todos os símbolos são alterados aleatoriamente, então parece polonês (ou qualquer outro idioma estranho). São sempre 2 caracteres certos, dois podem ser alterados, ...
Como o Windows e o Ubuntu se recusam a rodar com drivers nVidia (o xorg funciona com renderização de software), suponho que seja um problema com a placa gráfica. Talvez uma vez que ficou muito quente, eu não sei. Você disse que trocou a GPU, quer dizer a placa inteira ou apenas o processador? Porque eu também poderia imaginar que a memória de vídeo é responsável por isso. De qualquer forma, depois de meses eu finalmente desisti de pesquisar, pois funciona bem o suficiente para fazer alguma programação, escritório, internet e até mesmo vídeos e jogos 2D, para que eu possa viver com isso.