I've been dealing wiht this issues for a couple of weeks now on multiple machines - Xp and 7, 32 and 64bit units. I've tried the Hot Fix with no luck as well as stopping the update service, deleting the history and re-starting the service - Also no luck.
Here is how I finally got past it:
1) Type update in the Win 7 run box and choose Windows Update, or go through the Control Panel to get to the Windows Update screen
2) Under 'Download and install updates for your computer' it should say something like '24 important updates are available' (or how ever many updates your machine needs). Click on that sentence - You will see a list of the available updates.
3) Starting from the TOP of the list, deselect all of the updates except for the bottom three or four and hit OK.
4) You should now see the 'Download and install your selected updates' screen.
5) Hit 'Install updates'.
6) Let the updates install (it should be very quick since you are only doing three or four at a time). Restart the machine. The updates should completely install without issue.
Repeat the process, restarting after each small update until you have gone through the entire list.
We exclusively deploy Lenovo ThinkCentre machines that come with some bloatware including Norton and for a while I was convinced that the issue was some hidden Symantec piece that wasn't getting uninstalled (the first thing I do on our new units is to uninstall that incredible resource hog of a program) but now I think its a Microsoft issue where one update is trying to overwrite a previous update during the regular Update install process. Installing a few of the oldest updates first allows the data to be written without another update trying to overwrite it during the same install process.
This fix has now worked for me on a 32bit XP machine and a 64bit Windows 7 machine.