You are not missing anything here. The Energy will change if you change the dielectric and "hold everything else constant".
However, your statement.. holding all other variables constant.. is a little vague. Changing the dielectric will change the capacitance, there is no way around that other than to change the dimensions of the capacitor, which again violates your "holding all other variables constant" rule.
Instead I think you should be thinking of, "Don't change anything else." That is, the parameters may change, but not by any other introduced energy.
So lets say we have an isolated 1F capacitor previously changed with 1 Coulomb.
\$V = Q/C = 1/1 = 1V\$
and \$E = 0.5 * C * V^2 = 0.5 * Q * V = 0.5 * 1 * 1 = 0.5 Joules\$
Now lets double the permittivity of the dielectric
We now have a 2F capacitor, but the electrons did not move so the charge is still 1 Coulomb.
\$V = Q/C = 1/2 = 0.5V\$
and \$E = 0.5 * C * V^2 = 0.5 * Q * V = 0.5 * 1 * 0.5 = 0.25 Joules\$
That's right, we apparently just "lost" half the energy.
But what about the Law of Conservation Of Energy.
Ok you are probably screaming that is impossible because of conservation of energy laws. However we are talking about potential energy here. Potential energy is relative and dependent on space. If you change the space the energy value changes. It does not go anywhere, it simply is a different viewpoint.
If you have a tall tank of water the potential energy of the water is
\$E=1/2 * grA * h^2 \$
g = gravitational acceleration
A = area of water surface
r = water density
h = height of the water
Does that look vaguely familiar? It should.
If you change g you change the energy. But you did not touch the tank or it's contents. The same goes for a capacitor, changing the dielectric effectively changes the electrical "gravity" between the plates. Potential energy is now different.
Conservation of energy does not apply in these situations..
According to The Law of Conservation of Energy, and, specifically, Noether's theorem..
"Systems which are not invariant under shifts in time (an example, systems with time dependent potential energy) do not exhibit conservation of energy."
In this case since we change the dielectric at time \$T_0\$ the system energy is time dependent.
If you like, it is not that energy disappeared, but rather the "potential" energy it can generate has been reduced.
From your EDIT:
OK so if you want to hold the capacitor at a constant voltage what will happen.
Sufficient current will flow into the capacitor to maintain the voltage and the final new charge on our now doubled capacitor will also double to 2 Coulombs.
and Energy will be
\$E = 0.5 * C * V^2 = 0.5 * Q * V = 0.5 * 2 * 1 = 1Joules\$
So now the Energy returns to what we had before, but the charge changes.
Or to put it another way, the voltage supply will add in another half Joule to get it back up to the original voltage.
NOTE: The above also explains what happens with the other capacitor paradox where you discharge a capacitor into an identical capacitor and apparently "lose" half the energy. The difference being instead of changing the dielectric constant you doubled the area of the capacitor.