Sergio ha ragione, l'interprete java va a prendere come percorso di ricerca il percorso impostato nel CLASSPATH, se non trova nulla di specificato assume come percoso la directory corrente. Quindi fino a che non specifichi un CLASSPATH particolare tutto funziona bene, nel momento in cui decidi di farlo devi includere TUTTE le directory in cui l'interprete deve cercare i file .class da eseguire, e quindi fra le tante devi anche specificare la directory corrente, e cioe' ./
Questo non solo sotto linux.
Se vuoi fare una piccola verifica prova ad eseguire il tuo file con il comando
java -cp ./ nomeFile
il parametro -cp segnala all'interpretere il percorso per la sola sessione, nel qual caso la directory corrente ./
Chiaro?