Quantum indistinguishability using density operators

There is something that bugs me concerning the use of density matrices. For instance, to argue that quantum teleportation does not spread an information faster than light, Nielsen and Chuang state the following:

Measuring in Alice’s computational basis, the state of the system after the measurement is:

$|00rangle[alpha|0rangle+beta|1rangle]$ with probability $frac14$

[…]

$|11rangle[alpha|1rangle-beta|0rangle]$ with probability $frac14$

They then proceed to compute $rho^{AB}$ and trace out Alice’s system to find $rho^B=frac12I$, indicating that Bob has no information whatsoever on the state until Alice gives him the results she got with her measurement.

I struggle to understand how to compute the density matrix here, or more exactly why "the system is in state x with probability y" allows to compute it. Once Alice measures the state, she knows the state Bob’s system is in. I reckon that Bob doesn’t, but what about the following scenario?

Let us call the previous Alice and Bob Alice1 and Bob1 and the following ones Alice2 and Bob2.

Alice2 prepares a $n$-qubit basis state $|xrangle$. She sends this register to Bob2, who measures it (to learn $|xrangle$ with probability 1 since $|xrangle$ is a basis state) creates a $n$-qubit basis state $|hrangle$ chosen uniformly at random, CNOTs it with Alice2’s register and sends back to Alice2 her register, without telling her what $|hrangle$ is. Hence, Bob2 knows that the total system is in state $|xoplus hrangle|hrangle$. In particular, these registers being not entangled, Bob2 knows exactly the state Alice2’s system is in, just like Alice1 knew Bob1’s state. However, from the point of view of Alice2, the system can be in any basis state with uniform probability. Hence (this is where, I think, the error is), her density matrix is identical to the state of a uniform superposition of basis states, that is:
$$rho^{A_2}=sum_i|iranglelangle i|$$.
There are now two contradictory things that come to my mind:

1. Since Alice2’s density matrix is the same as if she created the state $mathbf{H}|0rangle$, applying $mathbf{H}$ and measure should return $|0rangle$ with probability 1. However, Bob2 knows that it will give $|0rangle$ with probability $2^{-n}$. Hence, it is high likely that Alice won’t obtain what she expects, leading to an inconsistency.
2. When carrying out the computation, here’s what I got. We have (up to a normalisation constant):
   $$mathbf{H}=sum_{a,b}(-1)^{acdot b}|aranglelangle b|,.$$
   Hence, after having applied $mathbf{H}$, the density matrix becomes:
   $$mathbf{H}rho^{A_2}mathbf{H}^dagger=sum_{a,b,x,y,i}(-1)^{acdot b}(-1)^{xcdot y}|aranglelangle b|iranglelangle i|xranglelangle y|$$
   which can be reduced to:
   $$mathbf{H}rho^{A_2}mathbf{H}^dagger=sum_{a,y,i}(-1)^{(aoplus y)cdot i}|aranglelangle y|$$
   which can be reduced to:
   $$mathbf{H}rho^{A_2}mathbf{H}^dagger=sum_{a}|aranglelangle a|,.$$
   hence Alice, will measure $|0rangle$ with probability $2^{-n}$ which is consistent with Bob’s point of view. However, this raises the inverse problem: why, if the density matrix is equal to the one of $mathbf{H}|0rangle$, don’t we get $mathbf{H}rho^{A_2},mathbf{H}^dagger=|0ranglelangle0|$? (This question also applies generally, since, I think, I started with the density matrix corresponding to $mathbf{H}|0rangle$, I expected the result to be $|0ranglelangle0|$)

I think these inconsistencies comes from a misunderstanding of mine at some point of the density matrix properties, but I can’t see at which point is my reasoning flawed (though I have a guess, see in the text).