Assuming that you used the JRE offline installer of the latest version of JAVA (1.5.0_07) and it was this that failed (having uninstalled all previous versions and rebooted before attempting to in the new one), I'd try to install Java while booted in Save Mode. Maybe that will allow you to install it.
Taking a look at any of your security programs possibly preventing Java from installing properly would also be a good idea.
