Short answer: The new aerodynamic ceiling is 40,000 ft density altitude.
Constant Temperature Condition
It is instructive to imagine the following scenario: The aircraft is flying at the coffin corner at 35k feet (density altitude).
$L = W = ½ \cdot ρ \cdot V² \cdot C_lmax \cdot S$
The 'W' represents weight (in Newtons), which we are assuming to be equal to lift. In this case, the 'V' (TAS) is at it's maximum limit, which cannot be exceeded without having a shock stall (and a subsequent collapse in $C_l$). 'V' is also at it's minimum limit, which cannot be subceeded since that requires an increase in $C_l$, which is not possible since $C_l$ already equals $C_lmax$. It can be seen that any change in 'V' would ultimately result in a stall.
Now reduce the weight by 20% (W' = 0.8W), this means that the $C_l$ will be 80% $C_lmax$. If the aircraft is slowed down now, it won't stall, since there is a headroom available in $C_l$. This will also alter the shock stall speed (shock stall speed changes with $C_l$), but for the purposes of this question, it does not make any difference, and so we will assume that it doesn't change.
Now, we will start a climb at a constant Mach number - the same Mach number that we had earlier in the coffin corner. Doing so ensures that we never exceed the Mach number for shock stall (we're basically climbing alongside the buffet boundary). At some point in the climb, the aircraft will again attain the $C_lmax$ (stall boundary intersects buffet boundary), and will again find itself in the coffin corner - the altitude at which this happens is the new aerodynamic ceiling.
Since in the question we started at 35k feet, the aircraft was basically at tropopause, and so we can assume that the temperature is constant throughout the climb (how convenient is that!). This means that the Mach number of the aircraft varies ONLY with TAS - this also means that a climb at a constant Mach number is same as climb at a constant 'V' (TAS). And with that, this particular case is solved:
$W = ½ \cdot ρ \cdot V² \cdot C_lmax \cdot S$
removing all the constants from this equation (including 'V'), we get the following relationship:
$W ∝ ρ$
And so reducing the weight by 20% reduces the minimum necessary density $(ρ)$ by 20%. Which altitude has 20% less density than that at 35k feet? According to ISA charts, that altitude is 40k feet.
ISA Chart
Variable Temperature Condition
In the previous case, we conveniently assumed that the temperature was constant, and so a climb at constant Mach number was the same as that at a constant TAS. This is not always true, so let's look at a more general case.
Consider the same previous case of climb at constant Mach number, except that 'V' is no longer constant; as the altitude is increasing, the temperature and thus the speed of sound (a) are decreasing. For a constant Mach number, a reduction in 'a' requires a reduction in 'V'. From the previous equation, if we again remove all the constants, we get:
$W ∝ ρ \cdot V²$
'V' was not removed this time since it is no longer a constant - it's a variable, the value of which is not obvious (again, V is reducing as altitude is increasing). However, it is possible to substitute it with something known... We are climbing at a constant Mach number. What is Mach number?
Mach number $(M) = V / a$
$or, V = M \cdot a$
What is 'a' (speed of sound)?
$a = √(γ \cdot R \cdot T)$
This implies that:
$V = M \cdot √(γ \cdot R \cdot T)$
Again, removing all the "unnecessary" constants from this equation, we get the following relationship:
$V ∝ √T$
or $V² ∝ T$
Simply substituting this into the previous relation, we get:
$W ∝ ρ \cdot T$
Where 'T' is the absolute temperature (in Kelvin). Now as we can see, there are two variables to worry about: $ρ$ and T. But that's not a huge problem, since each altitude generally corresponds to a particular density and a particular temperature. By looking up these two values in the chart, the new aerodynamic ceiling can be determined for a given change in weight.
