Wow. No wonder Java is such a piece of crap. They can't even write their installer properly.
Install failed because one of the files to be updated did not match what the installer expected. The installer showed an appropriate error, but then proceeded to jump to the "Installation Successful" screen.
Add/Remove programs said I had 7u67, but when I actually ran the uninstaller it reported that I was still on the old version.