Нет причин, по которым все потоки не могут использовать один и тот же Random. Однако, поскольку класс не является явно поточно-ориентированным и поддерживает последовательность псевдослучайных чисел через начальное число. Несколько потоков могут заканчиваться одним и тем же случайным числом. Было бы лучше создать несколько рандомов для каждого потока и посеять их по-разному.
РЕДАКТИРОВАТЬ : Я только что заметил, что реализация Sun использует AtomicLong, так что я думаю, что она поточно-ориентирована (как также отметил Питер Лори (+1)).
EDIT2 : OpenJDK также использует AtomicLong для начального числа. Как уже говорили другие, полагаться на это все же нехорошо.