I was experiencing the same problem on my network, when attempting to upgrade the McAfee Agent from version 126.96.36.1995 to 188.8.131.524 using a startup script and 'FramePkg.exe /UPGRADE'.
In the end I discovered that there is a quite easy way to discover whether a client has the issue or not, and to fix the problem as necessary. I have written a script in KiXtart which I will attach to the end of this post to detect whether the problem has manifested itself on a client and automatically fix it for you. But first, some background knowledge about the problem and its effects:
On a machine where the problem has manifested itself:
As far as I can see, the reason why the problem occurs is that something goes wrong during the upgrade process, which means that although the agent files themselves are updated correctly, the internal Windows Installer database on the system is not updated with the new version, and so the computer 'thinks' that the old MSI file is still installed, instead of the new one. This causes problems during upgrades because the agent attempts an uninstall first, and this fails when Windows Installer is unable to find the MSI file for the 'old' version of the agent in the place that it expects, i.e. "%ALLUSERSPROFILE%\Application Data\McAfee\Common Framework\MFEAgent.msi'. I don't know why this should happen, but as someone else suggested before I should imagine it is some sort of race condition in a multi-threaded process, and I don't think it is likely to be Microsoft's fault. However, the fix for the problem is fairly simple - copy over the 'old' version of MFEAgent.msi into "%ALLUSERSPROFILE%\Application Data\McAfee\Common Framework" and attempt an upgrade again, and everything should be hunky-dory. You may want to do a FramePkg.exe /FORCEUNINSTALL first to get rid of all the half-installed agent files and registry settings as well, and then reinstall the agent from scratch just to be safe, but in my experience this is not strictly necessary and just copying over the correct version of MFEAgent.msi to match the current version that Windows thinks is installed seems to do the trick.
So what does my script do?
Basically, first it finds the current version of McAfee Agent from the 'Version' key that I mentioned above in the registry - i.e. the last version that installed successfully. Then it finds out the agent version of MFEAgent.msi in "%ALLUSERSPROFILE%\Application Data\McAfee\Common Framework", by extracting 'AGENTVERSION' from the Property table of the MSI file itself. Then it compares the two version to see if they match, and if they don't, it tries to copy the 'correct' version of MFEAgent.msi from a subfolder placed next to the script (which you have to create & copy yourself), using a copy of Robocopy.exe renamed to Setup.exe which is also stored in the same folder as the script (which you also have to download & copy/rename yourself).
(The last bit with Robocopy.exe is necessary due to McAfee's wonderful Access Protection Rules that are implemented in most versions of VirusScan, which will prevent you from using the KiXtart COPY function or any other function to overwrite the MFEAgent.msi file, as it is considered a 'protected' file. By renaming Robocopy.exe to Setup.exe, we are using one of the 'excluded' process names to bypass this rule, which is a bit naughty, but the only way I could see to do it without having to switch off the VirusScan protection rules).
So basically to use the script, you need to get a copy of KiXtart (http://www.kixtart.org/), get a copy of RoboCopy (http://tinyurl.com/4k28b), and get a copy of the relevant MFEAgent.msi files for previous versions of the McAfee Agent (from computers that haven't been updated yet), and copy them in a structure like this:
If you didn't have a version of the agent installed, you don't need to get an MSI or create a folder for it. Also the script won't fall over if it can't find an MSI file for a version that is installed - it will just say 'No corrected MSI file found for <versionnumber>, so you can add it in at a later date.
Feel free to modify the script or rewrite it in another language if you want to - it's in the public domain, I just want to be helpful. I have been running this exact script in my environment for about a week, and it has fixed the problem on all of my PCs, so I am pretty sure it will fix it for others as well (although if it doesn't, I can't offer you any support of course - it's entirely at your own risk!)
I hope this helps some people get this problem fixed. Hopefully McAfee will recognise the problem soon and sort out a patch themselves, but until then it's up to us, so please let us know how you get on, and post back to the forum with any other results / advice.