Random.Next() always returns 0

Random isn't thread-safe. You should use a different instance of Random for each thread, instead. I wouldn't suggest locking as you've suggested, as otherwise if that's a significant part of your overall time, it could end up being no faster than running it in a single thread to start with. Instead, you can use a thread local variable to have a separate instance per thread - taking care to ensure that you don't accidentally use the same seed for all the instances, which would give you the same sequence of of numbers in each thread.

See my article on randomness for more details, including sample code.