1. Run the MSI with verbose logging enabled

 

msiexec /i "{Path to msi}.msi" /L*V "c:\myLog.log"

 

2. Open the log file that was produced from the above command and copy the GUID that is shown in the line

 

FindRelatedProducts: Found application: {FB0B54D2-9C47-4196-BF0E-B6EEBF754E22}

 

Using the copied GUID, run the following command

 

msiExec /x {FB0B54D2-9C47-4196-BF0E-B6EEBF754E22}

 

At this point, the old service was uninstalled and I then proceeded to install the service with MSI without any issues. Hope this helps.