You mention "3 new time machines that we tried".
Might you actually be referring to Apples "Time Capsules".
I ask because Time Machine is a 'Software' application, part of OS X, whereas Time Capsules are a HDD device used for backups.
My other question is why is Apple replacing your Mac minis if it is the Time Capsules that are failing?