A/B testing and gradual rollout of features are a part of the Amazon software development culture. They use a system called
Web Lab to run "experiments" and many new Kindle features are enabled through this process.
Each device checks Amazon's servers periodically to determine which group it is in with respect to experimental features. A device has to be in the correct group in order for a feature to appear.
Amazon seems to be slowly adding devices to the group that enables the lock screen cover feature. I suspect that restarting the device triggers it to check its Web Lab status sooner than it would normally do so, leading to a greater chance of seeing this feature enabled following a restart.