I had a similar problem with one of the machines I have at home. I also tried running JavaRA to clean up previous version of Java that might have been installed incorrectly, but to no avail. What worked for me was deleting the folder that had the JRE inside. It should be located in a similar directory as this:
Completely remove that folder, then remove the folder:
After deleting these two files, empty your recycle bin and restart your system. Upon restarting, download the latest version of Java from this location:
Download Java for Windows Firefox
Installation should be smooth. Sorry if this is a bit simple and crude of a solution, but it worked for me, so it's worth a try. If by chance those two files that need to be removed are not there, it might have something to do with your registry.