It is true that unitary evolution cannot destroy information. This is the content of the no-cloning theorem and its time reversal - the no-deleting theorem. The no-hiding theorem says something different and more subtle.
Information hiding
In order to understand what it says it helps to start with the observation that classical information residing in a composite system $AB$ may be absent from $A$ and absent from $B$ simultaneously. The information may be hiding in the correlations between $A$ and $B$. The example used by Braunstein and Pati in their paper is a message encrypted with the one-time pad cipher. In this case $A$ is the cryptogram and $B$ is the key. Clearly, the message resides in $AB$. However, as was shown by Shannon, neither $A$ nor $B$ alone carries any information about the encrypted message.
No-hiding theorem
The no-hiding theorem says that the above situation is not possible for quantum information. More precisely, suppose we have a system $A$ in state $\rho_A$ and wish to hide this state by having it unitarily interact with environment $B$ in such a way that the post-interaction state of $A$ is constant, i.e. independent of $\rho_A$. The no-hiding theorem asserts that there exists a subspace of $B$ that is in state $\rho_A$. Consequently, and in contrast to the classical case, the initial state $\rho_A$ may be recovered by local operations on $B$ only.
Thus, the only way to hide quantum information is by moving it to another system. Unlike in the case of classical information, hiding information in the correlations between $A$ and $B$ is not an option.
Measurement
The situation described in the question is not a counterexample to the no-hiding theorem because the theorem concerns consequences of unitarity and measurement is not unitary.
(N.B. measurement followed by a classically controlled $X$ gate also appears to accomplish $|\psi\rangle|\psi\rangle \to |0\rangle|\psi\rangle$ which is prohibited by the no-deleting theorem. Once again, this is not a counterexample since the no-deleting theorem concerns unitary processes.)
That said, the restriction of applicability to unitary processes is weaker than it might first appear. Generally speaking, when we describe a situation using quantum mechanics we designate - usually implicitly - one of the systems as the observer. This choice determines how the postulates of quantum mechanics are applied. Specifically, when two systems interact neither of which is designated as the observer then we apply the postulate of unitary evolution to describe the interaction. However, to describe an interaction involving the observer we use a different rule - the measurement postulate - and this is where non-unitarity, non-determinism and wavefunction collapse all enter the picture.
Now, the reason that non-unitarity of measurement is a weaker restriction on the no-go theorems than may initially appear is that every measurement may be described as a deterministic, unitary process by reassigning the designation of the observer to a different system. This is demonstrated by the Wigner's friend thought experiment.