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.