When you try to remove Java, do you see an error something like 'fatal error during installation'?

Check out post #11 in the thread below. The first link in post #11 has info about a MS cleanup utility - see whether that helps at all
http://www.gnutellaforums.com/genera...ease-help.html