Stavi eseguendo la procedura corretta dal Pannello di controllo, ma il pulitore del registro ti ha combinato un bel guaio (il tuo pulitore non ha una funzione di restore delle voci cancellate?).
Fermo restando il consiglio di michro (e anche quello mio: cambia pulitore!) prova a reinstallare l'ultima versione di Java.
Se risolvi è tutto ok, altrimenti io - al posto tuo- comincerei a pensare di rivolgermi ad uno dei suddetti Forum o ad una formattazione (IE ti serve per il Windows Update, ad esempio).
Ciao.