As you've seen, using the time to generate unique filenames doesn't work. A common work-around is to concatenate the time and the process ID (you're only generating one per process, right?), the reasoning being that it's not possible to have two processes with the same ID at the same time.
In theory, it might be possible to spawn processes fast enough and which die fast enough to cycle through all the available IDs in one second, so that's not really a very good solution either.
I would recommend that you look at Data::UUID which claims to be an implementation of a standard method which is guaranteed to work, and which claims to support allocating very large numbers of IDs.