If you are calling srand() before forking (or not calling srand) then the children have the same random seed as they start

Actually, if you don't call srand at all, the children will have different seeds as long as you don't call rand() before the fork() either (since perl 5.004). See perldoc -f srand:

If srand() is not called explicitly, it is called implicitly at the first use of the "rand" operator.

In this case, it's probably safest to call srand after the fork() anyway.