Descobri esta noite, embora eu achasse que tinha feito isso antes. Reiniciei meu laptop com tudo desligado (gadgets e tal) e abri a HP Update sozinho (Iniciar > Atualização HP). Não selecionei tudo, exceto o patch "Corrigir instalação cancelada" e cliquei em Avançar. Ele baixou o 512K que precisava, e me levou a instalar (normalmente o cancelamento de downloads). Eu terminei a instalação com os prompts.
Eu consegui iniciar o HP Update novamente e tudo parece estar sendo instalado sem problemas.