I maintain an open source project called IsWiX that provides templates and designers to accelerate the WiX / MSI learning and development process. One of the many things these templates do out of the box is provide proper Major Upgrade support. Consider this code generated by the template:
Code Source
<?xml version="1.0" encoding="UTF-8"?>
<Wix xmlns="http://schemas.microsoft.com/wix/2006/wi">
<!--
MSIProductVersion is defined in DesktopApplication.wixproj as 0.0.1 for local desktop builds.
You should pass in the MSBuild Property 'MSIProductVersion' to override it during an automated build.
See http://msdn.microsoft.com/en-us/library/windows/desktop/aa370859%28v=vs.85%29.aspx for information on allowable values.
The Product@Id attribute (ProductCode Property) will be a random GUID for each build. This is to support "Major Upgrades" where each install
is a seamless uninstall/reinstall.
-->
<Product Id="*" Name="DesktopApplication" Language="1033" Version="$(var.MSIProductVersion)" Manufacturer="DesktopApplication" UpgradeCode="7220a19b-ed49-4cd1-8002-6af7926441b4">
<Package InstallerVersion="301" Compressed="yes" InstallScope="perMachine" />
<MediaTemplate EmbedCab="yes" />
<!-- Major Upgrade Rule to disallow downgrades -->
<MajorUpgrade DowngradeErrorMessage="A newer version of [ProductName] is already installed." />
<!--Common Launch Condition-->
<!-- Examples at http://wixtoolset.org/documentation/manual/v3/customactions/wixnetfxextension.html -->
<PropertyRef Id="NETFRAMEWORK40FULL"/>
<Condition Message="[ProductName] requires .NET Framework 4.0.">Installed OR NETFRAMEWORK40FULL</Condition>
<!-- Include User Interface Experience -->
<Icon Id="Icon.ico" SourceFile="Resources\Icon.ico"/>
<Property Id="ARPPRODUCTICON" Value="Icon.ico"></Property>
<UIRef Id="UI"/>
<!-- Include Features and Directories Fragment -->
<DirectoryRef Id="INSTALLLOCATION"/>
</Product>
</Wix>
In addition to be documented in the comments, it's also discussed in the tutorials.
In a nutshell, you need to keep UpgradeCode the same and randomize ProductCode.