I think it's a combo of the recovery feature perhaps buggering things up (system restores can wreak havoc on the registry- one reason I recommend never using them) and your update patch being a bit outdated. Perhaps Microsoft has figured it out and cut off the patch so to speak. That particular patch is updated regularly.
What you can do is download the monthly security isos for free and with no WGA and install them or look up the updates contained in each one and install them manually.
You can find the monthly security isos here:
Security updates are available on ISO-9660 DVD5 image files from the Microsoft Download Center