Gauge Invariance of the Hamiltonian of the electromagnetic field
I will try to slightly elaborate on @VladimirKalitvianski answer.
From Maxwell's equations, we can derive that the following combination of gauge transformations on $\mathbf{A}$ and $\Phi$ leave both $\mathbf{B}$ and $\mathbf{E}$ invariant: \begin{align} & \mathbf{A}'=\mathbf{A}-\mathbf{\nabla} \alpha \\& \Phi'=\Phi+\frac{\partial \alpha}{\partial t} \end{align} where $\alpha=\alpha(\mathbf{x},t)$. This means that all the field configurations of $\mathbf{B}$ and $\mathbf{E}$ related by a gauge transformation are physically equivalent. Note that this has nothing to do with the Hamiltonian operator in QM.
Now in QM, we know that a wave function can always be multiplied by a phase factor: $$ \psi'=e^{-iq\alpha}\psi, $$ where $\alpha \neq \alpha(\mathbf{x},t)$, because the probability of finding the particle at a particular position is unaffected by the above transformation, and also the Schrodinger equation and the probability current are unaffected by the above transformation. If we now demand that the above also holds for when $\alpha = \alpha(\mathbf{x},t)$ (i.e. a gauge transformation), then the Schrodinger equation must be made gauge invariant: \begin{equation} i\frac{\partial\psi}{\partial t}=-\frac{1}{2m}(\mathbf{\nabla}-iq\mathbf{A})^2\psi+(V+q\Phi)\psi \end{equation} such that the Schrodinger equation is invariant under the simultaneous gauge transformations: \begin{align} &\mathbf{A}'=\mathbf{A}-\mathbf{\nabla} \alpha \\& \Phi'=\Phi+\frac{\partial \alpha}{\partial t} \\& \psi'=e^{-iq\alpha}\psi \tag{1} \end{align} Note that we can say that we have adjusted the "normal" Hamiltonian by replacing the ordinary (partial) derivatives by: \begin{equation} \begin{array}{cc} \displaystyle \mathbf{\nabla} \rightarrow \mathbf{D}\equiv \mathbf{\nabla} - i q \mathbf{A} \; ,& \displaystyle \frac{\partial}{\partial t} \rightarrow D^0 \equiv\frac{\partial}{\partial t} + iq \end{array} \end{equation} To sum up, by demanding that our theory is invariant under the gauge transformation expressed by equation $(1)$, we are forced to change the Hamiltonian operator as we have done above. However, by doing this, the new Hamiltonian describes a particle interacting with the potentials $\mathbf{A}$ and $\Phi$. If you're not convinced by this argument, I strongly recommend you to read up on the Aharonov–Bohm effect (http://en.wikipedia.org/wiki/Aharonov%E2%80%93Bohm_effect).
Furthermore, note that we require that a gauge transformation does not affect any observables. This means that we must demand that the probability current is also unaffected. You can show (although it is quite tedious) that the current is made gauge invariant by making the replacement: $\displaystyle \mathbf{\nabla} \rightarrow \mathbf{D}$.
What is physical meaning of gauge non-invariance of potentials $\mathbf{A}$ and $\phi$? Following their definitions, only their differences matter, not the absolute values, to be short.
The distance between two points is also invariant, but the liberty in choosing the frame reference position is translated into non invariance of a single point position.