Eu tive exatamente o mesmo problema descrito por RaphaelVidal. No meu caso, a solução foi realmente simples.
A causa do problema parece ser um download cancelado ou a instalação de uma atualização anterior. Eu pude ver que no histórico de atualização (veja o lado esquerdo no Microsoft Update) que uma atualização anterior foi cancelada.
Nesse histórico, é exibido um "número KB" dessa atualização cancelada.
A solução é para o Google nesse "+ download + Microsoft". E então baixe e instale essa atualização manualmente.
Depois dessa instalação, no meu caso, o Microsoft Update estava funcionando novamente.
(Talvez você veja mais atualizações canceladas no histórico e você deve repetir o que precede).