Trouble installing Java - Unable to verify the security integrity

Let's say you get this error:

---------------------------
Error - Java(TM) Update
---------------------------
Unable to validate security integrity on the file. File is either corrupted or unsigned.
---------------------------
OK
---------------------------

And you go to www.java.com and do the "Free Java Download" ... installing it gets this:
---------------------------
Error - Java(TM) Installer
---------------------------
Downloaded File C:\Documents and Settings\username\Application Data\Sun\Java\jre1.6.0_17\jre1.6.0_17-pfrom15.msi is corrupt.
---------------------------
OK
---------------------------

What to do?
Go to the Manual Download section and download the Offline install (second link) (It should look similar to jre-6u17-windows-i586-s.exe)

If that doesn't work, drill down and find the jre .msi file and install that.