Samba operations return NT_STATUS_INVALID_SID after initial setup

I am setting up Samba as sole AD controller for a new domain following the official instructions. Everything appears to go fine with the domain provisioning, and I can get a kerberos ticket with kinit just fine; after that, however, things fail:

$ kinit administrator@EXAMPLE.COM
Password for administrator@EXAMPLE.COM: [OK]

$ klist
Ticket cache: FILE:/tmp/krb5cc_0
Default principal: administrator@EXAMPLE.COM

Valid starting       Expires              Service principal
05/17/2016 23:36:39  05/18/2016 09:36:39  krbtgt/EXAMPLE.COM@EXAMPLE.COM
    renew until 05/18/2016 23:36:36

$ smbclient -L localhost -U%
session setup failed: NT_STATUS_INVALID_SID

When attempting to join a windows desktop to the domain, I get a similar error:

The following error occurred attempting to join the domain "example.com":

The Security ID structure is invalid.

I see nothing enlightening in the logs and google has failed me too. My suspicion is that I'm missing a dependency not covered by the package system -- e.g. the package description notes that winbind is required for it to operate as an AD DC even though it's not a package dependency. Perhaps something else is too.

This is samba v4.3.9 running on Ubuntu 16.04.