Same problem here. I am running CC v 5.07.5261 (64bit) in a new clean install of Win7 64bit.
Also just to be clear, removing those reg keys does not cause Reader DC to re-install. It just does a reconfigure or setup. But, certian things I set in Reader Prefs persist across the Cleaner fix and the restart of Reader. So it is not clear what it is doing when it needs to re-setup, as those items in prefs do not go back to default.
Also #2: I excluded the suggested key:
HKCR\Interface\{9B4CD3E6-4981-101B-9CA8-9240CE2738AE}
and it had no effect. Issue is still there.
But, I am running USA/Eng versions of all of the above, so perhaps the key is different.
AND, here is the kicker. When I first installed Reader DC, and then used CC none of this was going on. After about 2 or 3 weeks of this new install running the problem came up. I wish I could pin it down to some change, but I don't run the Reg cleaner part of CC that often.
bc