You don't mention the KB # but is it by any chance KB955428? A lot of people have been having problems with it. I even opened a case file with Microsoft Support which I now have to close.

Try installing the update using this link:
http://www.microsoft.com/downloads/details.aspx?FamilyID=458985c3-9c6f-4049-81cd-0d0389c81f11&DisplayLang=en You'll have to right-click, go to Properties and unblock if you are using Vista with UAC. Unzip it to your desktop and double-click.
I don't know if there is a download option for your location.
I downloaded and installed "KB955428_en-US.cab", rebooted and in Vista, it is showing only in "Installed Updates" (not in "Update History").
In XP it just appeared in the list as usual.

Note: The installer gives the impression that nothing happened.....very annoying. You have to reboot to check whether or not it installed.