Per quanto riguarda la tua soluzione, ho notato solo ora che tu, nel main, generi due istanze della stessa classe.

Settando statico l'oggetto Random, fai in modo che entrambe le istanze condividano lo stesso oggetto, mentre avendo un oggetto non statico, ogni istanza possiederà la propria copia dell'oggetto.

A questo punto credo che le due chiamate siano effettuate talmente velocemente che il seed (seme) viene impostato allo stesso valore (anche se la cosa mi suona abbastanza strana). Il costruttore vuoto di Random, infatti, fa sì che il seme venga inizializzato con il valore di System.getCurrentTimeMillis() ed è possibile che tale valore sia uguale durante le due chiamate, istanziando due generatori uguali (probabilmente la granularità di System.getCurrentTimeMillis() non è sufficiente a garantire due valori diversi).

Ciao.