Why don't $A^TAx = A^Tb$ and $Ax=b$ have the same solution?

Every solution to $Ax = b$ is a solution to $A^T A x = A^T b$, but not the other way around. A solution to $A^T A x = A^T b$ need not be a solution to $Ax = b$, unless $A^T$ is invertible (which is often not the case in applications).

It seems to me that I could get from the first equation to the second equation by simply multiplying both sides by $A^T$, so in my conception this wouldn't change the solutions.

It's not what you're missing, but what you're adding. You can indeed get from the first equation to the second by multiplying both sides by $A^T$. This means every solution to the first equation is also a solution to the second equation.

But you are trying to say more: you are trying to say every solution to the second equation is also a solution to the first equation. But that doesn't follow from your observation.

To make that conclusion, you need to find some way to get from the second equation to the first one, or some other argument that would imply a solution to the second is a solution to the first -- and such a thing may not exist, meaning that the second equation really does have solutions that are not solutions to the first equation.

If $A$ is invertible, they will indeed have the same solution because you could go from the second equation to the first by multiplying by $(A^{T})^{-1}$. In general, however, the first may have infinitely many solutions, whereas the second will have a unique solution if you have only linearly independent columns of $A$. See Moore-Penrose pseudoinverse for more.