If it wasnt carbonated water here is two possible explanations:
If it wasn't carbonated, it's probably the supercooling effect. This is much the same as superheating, where water doesn't boil even though it's at 100°C. If the insides of the bottles were smooth enough and the water pretty pure (mineral water should do just fine for that), there's no place for the crystallisation to start, and thus the water stays liquid. By opening the bottle, dust and such enters the bottle, and the water turns to ice.
We suspect that what's happening here is that the water in the bottles which did not freeze overnight was "supercooled." Water normally freezes when it is cooled below 0 degrees Celsius, forming ice crystals. Ice crystals form more easily when they grow on existing ice crystals -- the water molecules like to pack themselves in place on a crystal that's already gotten started. It doesn't take much to start the crystallization process going -- a little piece of dust or other impurity in the water, or even a scratch on the bottle are sometimes all it takes to get ice crystals growing. The process of starting off a crystal is called "nucleation."
In the absence of impurities in the water and imperfections in the bottle, the water can get "stuck" in its liquid state as it cools off, even below its freezing point. We say this supercooled state is "metastable." The water will stay liquid until something comes along to nucleate crystal growth. A speck of dust, or a flake of frost from the screw-cap falling into the bottle are enough to get the freezing going, and the crystals will build on each other and spread through the water in the bottle.
Water releases 80 calories per gram when turning from a liquid to a solid. We suspect your freezer is only a few degrees Celsius below zero(perhaps ten or fifteen?), and the specific heat of water is one calorie per degree per gram. This means that your water, as it freezes, warms up the rest of the water until the process stops at 0 degrees Celsius, freezing perhaps ten or twenty percent of the water. This ice may be distributed throughout the bottle, though, as the crystallization process happens very quickly and heat flows slowly.
We suspect you have slush in your bottle rather than hard ice when this is done. You can compare with another bottle which froze hard in your freezer overnight how hard it is to squeeze the bottle and how long it takes to melt. The ice will also take up more room than the water it used to be, and some water may spill out the top.
There can also be some small effects of pressure and of dissolved gases on the freezing temperature. Is your water under pressure?