Sorry to tell you, but you are suffering from buffering ;-). Tie::File has its own buffering scheme (which I found out simply through reading the man page of Tie::File). Look for "Deferred Writing". The solution is to use the flush method of Tie::File at appropriate moments or turn of the buffer completely with tie @array, 'Tie::File', $file, autodefer => 0;.
UPDATE: moritz has the right answer. You might think about using a different copy of the file for each of the subprocesses, if your file isn't too big