isc-dhcp-server.service fails on xenial with "Can't open lease database /var/lib/dhcp/dhcpd.leases: No such file or directory"

While investigating a DHCP issue on MAAS, I installed a fresh xenial on a LXC container and installed the isc-dhcp-server package. It fails to start with a syslog entry like "dhcpd[8090]: Can't open lease database /var/lib/dhcp/dhcpd.leases: No such file or directory --.

From the machine:

root@xenial-dhcp-test:~# lsb_release -rd
Description: Ubuntu Xenial Xerus (development branch)
Release: 16.04

root@xenial-dhcp-test:~# dpkg -l isc* | cat
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name Version Architecture Description
+++-====================-==============-============-=====================================================
ii isc-dhcp-client 4.3.3-5ubuntu1 amd64 DHCP client for automatically obtaining an IP address
un isc-dhcp-client-ddns <none> <none> (no description available)
ii isc-dhcp-common 4.3.3-5ubuntu1 amd64 common files used by all of the isc-dhcp packages
ii isc-dhcp-server 4.3.3-5ubuntu1 amd64 ISC DHCP server for automatic IP address assignment
un isc-dhcp-server-ldap <none> <none> (no description available)

root@xenial-dhcp-test:~# systemctl status isc-dhcp-server.service
● isc-dhcp-server.service - ISC DHCP IPv4 server
   Loaded: loaded (/lib/systemd/system/isc-dhcp-server.service; enabled; vendor preset: enabled)
   Active: failed (Result: exit-code) since Tue 2016-01-19 23:43:40 UTC; 6min ago
     Docs: man:dhcpd(8)
  Process: 8090 ExecStart=/bin/sh -ec CONFIG_FILE=/etc/dhcp/dhcpd.conf; if [ -f /etc/ltsp/dhcpd.conf ]; then CONFIG_FILE=/etc/ltsp/dhcpd.conf; fi; exec dhcpd -user dhcpd -group dhcpd -f -4 -pf /run/dhcp-server/dhcpd.pid -cf $CONFIG_FILE $INTERFACES (code=exited, status=1/FAILURE)
  Process: 8081 ExecStartPre=/bin/chown dhcpd:dhcpd /run/dhcp-server (code=exited, status=0/SUCCESS)
 Main PID: 8090 (code=exited, status=1/FAILURE)

Jan 19 23:43:40 xenial-dhcp-test sh[8090]: Can't open lease database /var/lib/dhcp/dhcpd.leases: No suc...y --
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: check for failed database rewrite attempt!
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: Please read the dhcpd.leases manual page if you
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: don't know what to do about this.
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: If you think you have received this message due to a bug rather
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: than a configuration issue please read the section on submitting
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: bugs on either our web page at www.isc.org or in the README file
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: before submitting a bug. These pages explain the proper
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: process and the information we find helpful for debugging..
Jan 19 23:43:40 xenial-dhcp-test sh[8090]: exiting.
Hint: Some lines were ellipsized, use -l to show in full.