If I then try to start slapd using slapd -d 16383, it seems to start
up fine, but can't read the database.
Are you starting it with -d at the command line (perhaps as root), but the
init script uses -u slapd or similar non-root uid? It's very odd to me tha
the TLS complaint doesn't show up with -d, and I wonder about certificate
permissions.
I'd try slaptest and/or slapd -d config to make sure that's all sane,
again making sure to run it as the slapd user.