Eigentlich sollte es reichen wenn das alte Java über die Softwareverwaltung deinstalliert wird.
Funktioniert die Installation trotzdem nicht, befinden sich evtl. noch Einträge des alten Java Runtime in der Registry unter:

\Computer\HKEY_LOCAL_MACHINE\SOFTWARE\Classes\Interface

In diesem Zweig nach Einträge für den Runtime suchen und diese dann entfernen.

!Vorsicht!
Wer nicht genau weiß, was er macht sollte vorsichtig sein. Das Ändern der Registry kann die Stabilität von Windows beeinträchtigen, bzw. das ganze System lahmlegen.