Here are some things you can do to help troubleshoot the issue.
Turn on MSI verbose logging. Easiest way is to just run this (from an elevated cmd prompt of course).
msiexec /i your_package.msi /l*vx c:\package.log
Then when the package fails to install you can look for that fatal error and see what the deal is.
Now part of the Windows SDK is a tool called MSIZAP, which is great when you have an MSI package that wont uninstall from add/remove programs for some reason and you just want to say "To Hell with it" and blow the thing out of the water. So what can you do in the real world? Well luckily we have a free tool called Windows Installer CleanUp Utility, which is a long way of saying MSIZAP.exe
So when you run into a stale package that wont uninstall and you can't install over the top of it (terrible movie). Then try this tool out.
If you don't ant to use the GUI, well the install package also throws the msizap.exe tool in the same directory so then you could use:
C:\MSIZAP.exe T package_you_want_to_uninstall.msi
C:\Program Files (x86)\Windows Installer Clean Up>dir
Volume in drive C has no label.
Volume Serial Number is 50F2-E34D
Directory of C:\Program Files (x86)\Windows Installer Clean Up
02/06/2007 10:09 AM <DIR> .
02/06/2007 10:09 AM <DIR> ..
01/07/2004 11:04 PM 40,960 msicuu.exe
06/16/2006 03:21 AM 94,720 MsiZap.exe
09/06/2006 05:49 PM 7,062 readme.txt
3 File(s) 142,742 bytes
2 Dir(s) 100,753,727,488 bytes free