Fake malware scanners are extremely popular with criminals, as many users will pay the "blackmail" money to get the full version to remove the [fake] problems found (and of course, the problems still remain and then they have your credit card info, too).
What version of Windows are you running? What browser are your running (IE, Firefox, etc.) and what specific version of it do you have (look at it's Help>About menu choice)?
From what I can find out about that one, it's typical "drive by" type malware and shouldn't be infecting your Master Boot Record. But, even if it is, when reinstalling Windows, a new MBR (and Windows should be creating one by default) should fix it, if you're installing it in a way that recreates the partition table (and that varies by Windows version).
What you may want to do is use the Ubuntu Live CD you have and delete all partitions on the drive using the included partition manager (it probably has GParted in it's menus that you can use for that purpose). Then, reinstall Windows, letting it repartition the drive for you.
Or, zero out the MBR entirely first (you can use dd on the Ubuntu Live CD for that purpose and overwrite the first 512 bytes on the drive), just to make sure you don't have boot sector malware that's still there. But, let me know what Windows version you're running first.
How about removable media (USB Sticks, External Drives, etc.)? You may have malware on one of them that's loading when you plug in a device via autorun if you don't have that feature disabled in the version of Windows you're running now.
There are lots of ways to clean a drive, and you may be able to get rid of it without another reinstall using one of a number of malware scanners that can run from DVD or USB Stick. For example, Avira, Bit Defender, Dr.Web and others have free malware scanners based on Linux Live CDs that you can download and burn to CD or USB Stick and boot into to clean many of those types of problems. I keep some of them handy on a USB Flash drive for that purpose. That way (booting into a different operating system to run the scans), the malware isn't actually loading and able to evade the products you're trying to use to clean the infected machines.
Another technique is removing a drive and installing it in a known clean PC as a second drive. Then, use popular products (Malwarebytes, etc.) to scan the compromised drive (since you wouldn't be loading anything from it to clean it, as you'd be booting from a known clean drive with Windows installed).
But, I'd let us know more about your config first.