Hola.
De casualidad estás usando el método setSeed() con una constante?
Porque no nos muestras algo de código. Estás usando Threads? Como es la instanciación que haces de la clase Random?, ¿A qué te refieres con
"coloco 10 numeros nuevamente" estás ingresando algún dato? ¿Que versión del JDK estás usando? Por favor se más específico.
Ten en cuenta este apartado de la documetación de la clase Random:
If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers. In order to guarantee this property, particular algorithms are specified for the class Random. Java implementations must use all the algorithms shown here for the class Random, for the sake of absolute portability of Java code. However, subclasses of class Random are permitted to use other algorithms, so long as they adhere to the general contracts for all the methods.
Clase
RandomSaludos.