la Java di microsoft deve cmq essere lasciata installata...ho avuto lo stesso problema tuo utilizzando quel programmino per la rimozione e la soluzione č stata:
reinstallare la java di microsoft fino all'ultimo aggiornamento;
installare poi quella di Sun e, tramite pannello di controllo/installazione applicazioni dire al sistema di usare come predefinita quella di Sun!