I am not a user of this site really... but I haven't seen a fix to this problem... and so am posting here. Don't bother with SUN's instructions or with javafixer.com. Their fix your windows installer is actually bad advice in this case- premature!
The really problematic case where nothing works, happens when Java has been partially or fully removed but there is still one more installer left pointed to in the registry. Java Runtime could have been installed/reinstalled by multiple programs. And you may even have (or have had) several JREs in your machine, more than one pointing to the same JRE. When uninstalling, one of those JRE uninstallers (or something external) could have removed the JREs but it won't remove other "installed programs/uninstaller" entries in your registry. After doing the steps below, if you check your Add/Remove programs or just Programs in Vista/7 you will no longer see Java listed.
First search and find your windows/installer folder and delete the file that is your java installer. It is an exe file. You may need to unhide hidden files, give yourself admin access, ask to see protected system files etc through folder options. do all of that before deleting the installers. Next, open regedit and look a subkey which contains "Java" and "installer" in its data, in one of the values. Delete the whole thing. Recheck your registry so that there are no references at all to java. NOW and only now, install Java through the installer of your choice. It won't find any old installers to clash, and the error goes away. Believe it or not, SUN/Oracle HAVE NOT FIGURED THIS OUT AFTER YEARS!!! http://www.java.com/en/download/help/error_1723.xml
You don't really have to delete the installers- just the registry delete is enough. But, why leave a silly installer hanging around?
The fault in this whole mess is with SUN/Oracle in that they allow so many copies of JREs to coexist and be dropped in by every java application out there and don't maintain it uniquely, though the "Java Control Panel" is unique. So you have idiotic scenarios like different javas on your computer each trying to update it, while only one runs as the "real java" with websites and applications; and the crosscutting uninstalls end up happening one day. You bet this don't happen on Sun's own Solaris.
There is the alternative possibility of a faulty JRE installation or the corruption of your windows installer. For the first, search and delete everything manually and follow the steps above. For the second, you will need to delete it and get a new copy of the windows installer from microsoft.com
These are less likely to be the case. This is not a trojan issue for crying out load. Unless you consider Windows a virus and java a trojan.