Tente usar o Revo Uninstaller Freeware para desinstalar o Java.
Mais alguns conselhos: desative qualquer software anti-spyware ou antivírus em seu sistema durante a instalação. Sempre execute instalações usando "Executar como administrador" ou desabilite o UAC durante a instalação.
Veja os links a seguir:
Erro 1721: Existe um problema com este pacote do Windows Installer
Por que o Java não é encontrado no x64 Windows Vista após a instalação?