Reconnecting spinal nerves does not look impossible. But I don't see any other feasible way for people whose heads are cryogenically stored to have bodies again, except cloning a new body for them.
In general, the idea of producing a body that lacks the brain but has everything else intact is very rational. Its doubtless creepiness may wane with time.
I still expect that growing particular tissues and whole organs (like liver, or kidneys, or bone) will end up being a faster route to cloned organ replacement. In particular, a body takes like 20 years to grow to the "finished" state, and a separate organ could grow much faster.