There are two ways to fix this, and I found I had to do both steps to make it work.
1) Open Internet Explorer. Go to Tools > Internet Options > Advanced > Reset and reset all settings. Try the update again.
2) Open an administrator-level command prompt, and run the following:
FORFILES /P %WINDIR%\servicing\Packages /M Microsoft-Windows-InternetExplorer-*9.*.mum /c "cmd /c echo Uninstalling package @fname && start /w pkgmgr /up:@fname /norestart"