Perhaps I can give some insight into this.
@TomFace Occasionally, the Security Center service can take some time to initialize after a reboot (I've noticed it can take slightly longer after updates). I've personally seen this range from 30 seconds up to nearly 15 minutes. As long as the service isn't running, we are are in the "waiting to register state". This is why despite how many times you may restart, you will still see this issue, as each reboot means the service will have to start again. That is also why occasionally after reboots (relating to your 1 out of 10 mention).
There is also the other scenario, in which case I can see from the initial poster's image, that we are in the process of updating. Once the update is done, and as long as the security center service is running, registration should be fine and the message should disappear.
If the issue is still occurring with the two above scenarios out of the way, I suggest putting in a ticket so we developers can take a look at it.