Are you clicking the change button instead of the remove button by mistake. The change button will try and re-install.

Also have you removed the J2SE Developement kit along with the J2SE Runtime. I think you may need to remove both.

If you have a registry cleaner. I would suggest running it. If not "google" for one. There are free ones available.. It sounds like some things may have been messed up in the registry if the above doesn't help.

Let us know if it helped.

*edit* didn't see your double post, Sberlin probably has the best idea *edit*