They don't freeze, they vitrify. That's a very big difference.
http://www.alcor.org/cryomyths.html#myth2
We can debate the degree to which cryoprotectant perfuses the brain outside a laboratory test of tissue, but vitrification appears to preserve the fine structure of tissue very well:
http://www.brainpreservation.org/competitors/
There is evidence of synaptic preservation in preserved and restored nematodes:
http://dx.doi.org/10.1089/rej.2014.1636