I don't quite follow your reasoning of why the law is wrong. You say yourself "Te is assumed constant", yet you imagine that converting the Te from a constant to a variable could affect the result. However, if you change Te from a constant to a variable, Newton's Law of Cooling is null and void, because a simplification is that Te is constant, and that allows a lot of /dt's to cancel.

The law is correct for when you can assume a constant Te, for example an object within a fluid flow (like an airplane wing during flight). The problem is, for stagnant situations, convection plays a huge role in heat transfer within the air. Controlling convection is really really hard, and even harder in a scientific setting that needs to be reproducible. Also, when dealing with transition temperatures, various things need to be taken care of, such as supercooling. This can literally stop working if your beaker is slightly dirty. So the problem is there isn't a way to universally control the conditions for this experiment. However, I did find that the winner of the RSC paper had a suitable explanation that involves the presence of supercooling for the colder sample of water. Essentially, if the colder sample supercools, it will take slightly more time to freeze, because while it should have frozen, the ice does not have a nucleation site. On the other hand, the warmer sample does not supercool, and freezes upon reaching 0 C. This experiment only works if the temperature difference is slight, probably within 15-30 C. Quite ingenious really!

Edit: After reading the rest of the comments, air bubble/filtered water/de-ionized water all have great effects on ice nucleation and supercooling, which for me supports the winner's paper.