I just realized I used the working machine as the example for why things are broken. The reason the broken machine is broken is due to an off by one error
RMCP+ Cipher Suites : 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
Cipher Suite Priv Max : XXXaXXXXaXXXaXX
Here MAAS thinks cipher 3, 8, and 12 are enabled so it tries to use cipher 3. Because its not accounting for the missing cipher 0 what is actually enabled is cipher 4, 9, and 13. Thus your seeing the access denied error. Even if MAAS never disabled a cipher and supported all 17 ciphers you'd still see the same error due to MAAS not accounting for cipher gaps.
I just realized I used the working machine as the example for why things are broken. The reason the broken machine is broken is due to an off by one error
RMCP+ Cipher Suites : 1,2,3,4, 5,6,7,8, 9,10,11, 12,13,14, 15,16
Cipher Suite Priv Max : XXXaXXXXaXXXaXX
Here MAAS thinks cipher 3, 8, and 12 are enabled so it tries to use cipher 3. Because its not accounting for the missing cipher 0 what is actually enabled is cipher 4, 9, and 13. Thus your seeing the access denied error. Even if MAAS never disabled a cipher and supported all 17 ciphers you'd still see the same error due to MAAS not accounting for cipher gaps.