Still have a question on Java program

Thanks for the help you have given so far. I am hoping that the following info will help me solve my problem. I also printed out the instructions for UPDATED YUKWARE REMOVAL and will try to work through these instructions.
I did go to Sun Microsystems to download a Java program. Would it be possible that the old Java that was on the machine had a virus?
My AVG free reports the following messages when I run it:
Counter.class virus identified Java/byte verify C:\Documents a...
Verifier Bug Class Virus identified Java/byte verify C:\Documents a...
Web.exe Trogan horse Generic. UFN identified Java/byte verify C:\Documents a...
Worker.class identified Java/byte verify C:\Documents a...
Xeyond.class identified Java/byte verify C:\Documents a...
jar.jar -2ad 522e1-6c 267 identified Java/byte verify C:\Documents a...
and then it goes on to tell me that the virus is embedded and can not be removed.
The Sun Microsystems web site tells me now that I need to remove the old program to install a new Java, but with the virus I can't get all of the old Java off.
Should I take everything off of my machine and replace all of the original software, AVG free and then update the old software? Will that get rid of the virus?