Not sure whether this bug has been a recent regression; however, it may have become user-visible after the policy enforcement in bug 676624 was introduced.

The root cause is, I think, this discrepancy between the policy fetch request and the validation of its response:
* For the request, the |public_key_version| field is unset by the client whenever the policy cache file is lost. From the protocol structure, this means "the client doesn't have any key, the server should respond with the initial key provision".
* For the response validation, the cached policy key file is used whenever it's present. This means that the key provisioned with the fetched policy is treated as the "rotated" key, not as the "initial" key. This leads to the validation of the received key to be signed with the old cached key (via the |new_public_key_signature| field), which fails because the server sent nothing there.

I haven't thought much on the fix yet, but two possible directions that I see are:
A. Ignore the cached key whenever the cached policy file is missing/invalid.
B. Tweak the validation code to avoid some extra checks when the fetched key equals to the cached key.

Yes, if we've lost the policy, we probably should also ignore the cached key (allow any new key to be provisioned). In a world where signing keys are *themselves* signed by DMServer, there's not really any way to inject a bad signing key any more so not interested in validating vs the old key if policy is gone.