I was having troubles with the Credential Manager of Windows 8.1 with a new Samba 4.1.x AD. Even after upgrading to Samba 4.2 this wasn't fixed.
After clearing the BCKUPKEY_PREFERRED as mentioned here. The Credential Manager was working again.
I'd guess my stored key wasn't 2048-bit and my Windows declined it.
It might be useful to include this in dbcheck, as suggested by Andrew, to make sure the stored key has the correct size or regenerate it in case of failure.
*** Bug 11546 has been marked as a duplicate of this bug. ***