I once heard on a science radio show that evaporation (aka, less mass to freeze) is the key to the story.
That's part of it. Evaporation itself causes cooling, which is another part.
I remember trying to test the old wive's tale as a kid, by putting a tray of cold water and one of hot water in the freezer at the same time. I don't know which froze first, but the hot water tray only had half sized icecubes.