On a whim, because I haven't heard back from support, I tried running CCleaner as admin and the new license seems to have stuck. There had been no error message before about not being able to save the registration info. So it looks like there are at least three straight up bugs:
1) failure to save updated license/registration data does not produce an error message within the application
2) dialog prompting for a new key is hard coded to the old style key and won't accept new style keys
3) the ccleaner license key database doesn't have or provide all the licenses that have been p