To answer this properly one would need to know the kind of battery you were testing. It is true that a battery will last longer when it is kept cold because the reactions that produce electricity are slowed down. It also doesn't give out the same level of power.
I don't know what happened with your frozen battery. Perhaps in freezing some seals were ruptured and so it lost some of its chemicals, or else exposure of the battery's contents to air might have reduced its power.
It is also important that you wait until all batteries come to room temperature before testing.