The states at $\Phi$ and $\Phi + \Phi_0$ are related by a gauge transformation[1] and therefore the spectrum must be the same. For concreteness let's talk about electrons fixed to a ring of radius $R$. Parameterize the wavefunction $\psi$ by the arclength $l$. Periodicity requires that $$\psi(l +2\pi r) = \psi(l).$$ There is some hamiltonian $H$ on the ring - $H$ must be gauge invariant so it is a function only of the position $l$ and the guage invariant derivative $D = i\partial_l + A$, where $A$ is the gauge.
Now lets take the gauge transformation $A\rightarrow A+n/r$, $\psi \rightarrow e^{inl/r}\psi$. This respects the periodic boundary iff $n$ is an integer, so it takes eigenstates of the Hamiltonian to eigenstates of the Hamiltonian. Now using the relation $$\int A\cdot dl = \int_S \nabla\times A \cdot da = \int_S B\cdot da \equiv \Phi,$$ we see that our gauge transformation is equivalent to changing the flux quantum by $\Phi_0$.
Note that we could also use a try a gauge transformation of the form $A \rightarrow A +\frac{n+\theta/2\pi}{r}$. We can do this as long as we change our bondary condition to $$\psi(l+2\pi r) = e^{i\theta}\psi(l).$$ In particular we can transform the gauge field to zero and be left with no $A$ but with a nontrivial boundary condition above. So if you want, you can forget about the magnetic field and gauge field and think instead about a uncharged problem but with the "twisted" boundary condition. This should make sense - there is no magnetism in $d = 1$ so I should be able to basically get rid of $A$. The boundary condition is the only vestige remains.
[1] I'm calling it a gauge transformation but in the physical case of a ring threaded by flux this gauge transformation cannot be extended to all space. This follows from the fact that it changes the amount of flux threading the ring, but that is gauge invariant. However the electronic spectrum doesn't know that this transformation cannot be extended to all space, and so it still works.