All I did was remove the Java Runtime Environment. To do that, I went to the Control Panel, chose 'Add and Remove Programs' and chose to remove Java Runtime Environment Update 2. I didn't even need to remove the original installation (I tried but if failed...).
So there you go folks. If this is driving you to the point of insanity, as it was me, try removing the Java Runtime Environment. It's all good.