This is really a great question.
Take a look at the figure attached here. The circle indicates a 2-dimensional degenerate subspace at $\lambda=0$.
In red we indicate two possible basis states for the subspace. In blue we show another possible choice of basis states.
Now look at the curvy green lines, these are the states as they evolve for $\lambda > 0$. The green curves do not connect with the red states at $\lambda=0$. The perturbation series is a Taylor series, which is a continuous function (it's a polynomial), so there is no way to make the series go from the red states at $\lambda=0$ to the green states for $\lambda > 0$.
Clearly, we have to start the perturbation series at $\lambda=0$ with the blue states, because those connect up with the green ones when $\lambda > 0$. The green states are, by definition, eigenstates of the perturbed Hamiltonian, so the blue states at $\lambda=0$ must also be eigenstates of the perturbed Hamiltonian.
Degenerate perturbation theory states. We show the states as functions of the perturbation parameter $\lambda$ (green), and various choices of the unperturbed states (blue, red).