En el CLASSPATH no tendrías que tener el directorio lib del JDK, por que eso ya lo pone el. Y bueno, suponiendo que lo tienes, si tu .class no esta en ese directorio, obviamente no lo encuentra.
Para que te encuentre los ficheros del directorio donde estas (o los subdirectorios de donde estas si usas paquetes) has de poner un '.' en el CLASSPATH (.=directorio actual). Por defecto está en el CLASSPATH cuando este no tiene nada, pero como tu lo tienes puesto a algo, entonces no lo tiene.
S!
Edit: Re-edicion de frase que ayer no se como tenía los dedos, pero esa frase no la entendía ni yo
.