You're correct that the solutions don't come out precisely the same. However, if we look at Schrodinger's equation with the added constant,
$$ i\hbar \frac{\partial}{\partial t}|\psi\rangle = (\hat H+C)|\psi\rangle $$
we notice that if we let
$$|\psi\rangle = e^{-iCt/\hbar}|\psi'\rangle $$
then the Schrodinger equation becomes
$$i\hbar \frac{\partial}{\partial t}|\psi\rangle = e^{-iCt/\hbar}\cdot i\hbar \frac{\partial}{\partial t} |\psi'\rangle +Ce^{-iCt/\hbar}|\psi'\rangle= (\hat H+C)e^{-iCt/\hbar}|\psi'\rangle$$
Which simplifies to
$$i \hbar \frac{\partial}{\partial t}|\psi'\rangle = \hat H |\psi'\rangle$$
In other words, shifting the energy by some constant $C$ is equivalent to multiplying all of the states by the phase factor $e^{-iCt/\hbar}$. Because this unitary factor is applied to every state, it cancels out in all physical calculations (e.g. expectation values) and so does not impact the predictions of the theory.
Classical physics is insensitive to shifts in potential energy because measurable physical quantities depend only on derivatives of the potential. Similarly, quantum mechanics is insensitive to shifts in potential energy because measurable physical quantities depend only on inner products between states, and the transformation induced by the potential shift ($|\psi\rangle \rightarrow e^{-iCt/\hbar}|\psi\rangle$) is unitary, meaning that it leaves the inner products unchanged. Both of these are particular examples of the more general notion of gauge invariance.
